/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 5ms 2.375 MiB
#2 Accepted 7ms 6.355 MiB
#3 Accepted 6ms 6.262 MiB
#4 Accepted 7ms 4.332 MiB
#5 Accepted 330ms 6.375 MiB
#6 Accepted 318ms 6.48 MiB
#7 Accepted 314ms 6.375 MiB
#8 Accepted 336ms 6.375 MiB
#9 Accepted 287ms 2.625 MiB
#10 Accepted 304ms 6.457 MiB
#11 Accepted 1072ms 5.5 MiB
#12 Accepted 1208ms 5.332 MiB
#13 Accepted 273ms 5.441 MiB
#14 Accepted 243ms 6.5 MiB
#15 Accepted 823ms 6.559 MiB
#16 Accepted 927ms 5.652 MiB
#17 Accepted 1117ms 6.691 MiB
#18 Accepted 1055ms 5.125 MiB
#19 Accepted 2777ms 6.625 MiB
#20 Accepted 1300ms 7.469 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 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-04 18:40:02
评测时间
2017-11-04 18:40:02
评测机
分数
100
总耗时
12717ms
峰值内存
7.469 MiB