/ Randle /

记录详情

Wrong Answer


  
# 状态 耗时 内存占用
#1 Accepted 6ms 2.34 MiB
#2 Accepted 10ms 6.25 MiB
#3 Accepted 8ms 6.355 MiB
#4 Accepted 5ms 2.344 MiB
#5 Accepted 159ms 6.375 MiB
#6 Accepted 136ms 2.598 MiB
#7 Accepted 156ms 2.59 MiB
#8 Accepted 154ms 6.5 MiB
#9 Accepted 177ms 6.477 MiB
#10 Accepted 139ms 2.594 MiB
#11 Accepted 747ms 5.0 MiB
#12 Accepted 723ms 5.125 MiB
#13 Accepted 248ms 5.305 MiB
#14 Accepted 238ms 6.555 MiB
#15 Accepted 500ms 6.84 MiB
#16 Accepted 505ms 5.445 MiB
#17 Accepted 541ms 5.957 MiB
#18 Accepted 516ms 5.59 MiB
#19 Wrong Answer 755ms 6.75 MiB
#20 Accepted 952ms 6.809 MiB

代码

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long ll;
int maxh = 12;
const int maxn = 5000;
int n,m;
using namespace std;
int head[maxn],nex[100005<<1],dis[100005<<1],q;
ll w[100005<<1];
int dep[maxn];
struct edge {
    int a,b;ll w;
} edges[100005<<1];
int fa[maxn][15];
ll maxx[maxn][15];
inline ll min(ll a,ll b){
	return a<b?a:b;
}
inline ll max(ll a,ll b){
	return a>b?a:b;
}

inline ll read(){
    ll num;
    scanf("%lld",&num);
    return  num;
}
bool operator<(const edge &ed1,const edge &ed2) {
    return ed1.w<ed2.w;
}
void connect(int x,int y,ll z) {
    nex[++q]=head[x],head[x] = q,dis[q] = y;w[q] = z;
    nex[++q]=head[y],head[y] = q,dis[q] = x;w[q] = z;
}
void printAns(ll a,ll b) {
    if(a!=b) {
        cout<<"madoka"<<endl;
    } else {
        cout<<"Baozika"<<endl;
    }
}
int father[maxn];
int find(int a) {
    if(father[a]==a) {
        return a;
    } else {
        return father[a] = find(father[a]);
    }
}
void merge(int a,int b) {
    int ffa = find(a),ffb = find(b);
    father[ffa] = ffb;
}
void dfs(int a) {
    //cout<<a;
    for(int i = head[a]; i; i=nex[i]) {
        int to = dis[i];
        if(to!=fa[a][0]) {
            dep[to] = dep[a]+1;
            fa[to][0] = a;
            maxx[to][0] = w[i];
            dfs(to);
        }
    }
}
edge edgeq[6500];
long long rr;

void init(int update) {
    if(update) {
       for(int i = 0;i<=q;i++) nex[i] = 0;
		for(int i = 0;i<=q;i++) dis[i] = 0;
		for(int i = 0;i<=n;i++) head[i] = 0;
		q = 0;
       // sort(edgeq+1,edgeq+1+rr);
        for(int i= 1; i<=n; i++)father[i] = i;
        int need = n-1;
        for(int i = 1; i<=rr&&need; i++) {
            if(find(edgeq[i].a)!=find(edgeq[i].b)) {
                connect(edgeq[i].a,edgeq[i].b,edgeq[i].w);
                need--;
                merge(edgeq[i].a,edgeq[i].b);
            }
        }
    }
    
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<=maxh;j++){
            maxx[i][j] = 0;
            fa[i][j] = 0;
        }
    }
    dep[1] = 1;
    fa[1][0] = 1;
    dfs(1);
    for(int h = 1; h<=maxh; h++) {
        for(int i = 1; i<=n; i++) {
            fa[i][h] = fa[fa[i][h-1]][h-1];
            maxx[i][h] = max(maxx[i][h-1],maxx[fa[i][h-1]][h-1]);
        }
    }

}
ll ans(int a,int b) {
    ll ret = 0;
    if(dep[a]<dep[b]) {
        swap(a,b);
    }
    for(int i = maxh; i>=0; i--) {
        if(dep[fa[a][i]]>=dep[b]) {
            ret = max(ret,maxx[a][i]);
            a = fa[a][i];
        }
    }
    if(a!=b) {
        for(int i = maxh; i>=0; i--) {
            if(fa[a][i]!=fa[b][i]) {
                ret = max(ret,maxx[a][i]);
                ret = max(ret,maxx[b][i]);
                a = fa[a][i];
                b = fa[b][i];
            }
        }
        ret = max(ret,maxx[a][0]);
        ret = max(ret,maxx[b][0]);
    } else {
        return ret;
    }
    return ret;
}
void addLine(int a,int b,ll z) {
	//edgesq rr
	edge ed;
    ed.a = a,ed.b = b,ed.w = z;
    int index = upper_bound(edgeq+1,edgeq+rr+1,ed)-edgeq;
    for(int i = rr;i>=index;i--){
    	edgeq[i+1] = edgeq[i];
	}
	edgeq[index] = ed;
    rr++;
}
int main() {
    scanf("%d%d",&n,&m);

    for(int i = 1; i<=m; i++) {
        int x=read(),y=read();ll z=read();
        edges[i].a  =x,edges[i].b=y,edges[i].w=z;
    }
    sort(edges+1,edges+1+m);
    //zui xiao sheng cheng shu
    for(int i= 1; i<=n; i++)father[i] = i;
    int need = n-1;
    for(int i = 1; i<=m&&need; i++) {
        if(find(edges[i].a)!=find(edges[i].b)) {
            connect(edges[i].a,edges[i].b,edges[i].w);
            edgeq[++rr] = edges[i];
            need--;
            merge(edges[i].a,edges[i].b);
        }
    }
    init(0);
    int tt;
    scanf("%d",&tt);
    int updated  = 1;
    for(int i = 1; i<=tt; i++) {
        char str[10];
        cin>>str;
        if(str[0]=='g') {
            int x,y,z,w;
            if(!updated) init(1);
            updated = 1;
            x=read(),y=read(),z=read(),w=read();
            printAns(ans(x,y),ans(z,w));
        } else {
            updated = 0;
            ll x=read(),y=read(),z=read();
           // cin>>x>>y>>z;
           // cout<<x<<" "<<y<< endl;
           if(z!=998244353){
             	addLine(x,y,z);
		   }
        }
    }
    return 0;
}

信息

递交者
类型
递交
题目
玩游戏(CQ直辖市noip模拟赛联考) T2
题目数据
下载
语言
C++
递交时间
2017-11-06 09:27:00
评测时间
2017-11-06 09:27:00
评测机
分数
95
总耗时
6687ms
峰值内存
6.84 MiB