/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 5ms 2.25 MiB
#2 Accepted 7ms 6.367 MiB
#3 Accepted 4ms 2.375 MiB
#4 Accepted 7ms 4.25 MiB
#5 Accepted 382ms 6.5 MiB
#6 Accepted 321ms 6.5 MiB
#7 Accepted 324ms 2.602 MiB
#8 Accepted 331ms 2.598 MiB
#9 Accepted 306ms 6.5 MiB
#10 Accepted 343ms 2.719 MiB
#11 Accepted 1104ms 4.875 MiB
#12 Accepted 1120ms 5.0 MiB
#13 Accepted 207ms 5.086 MiB
#14 Accepted 203ms 6.434 MiB
#15 Accepted 862ms 5.0 MiB
#16 Accepted 884ms 6.625 MiB
#17 Accepted 1020ms 6.832 MiB
#18 Accepted 1034ms 6.312 MiB
#19 Accepted 2762ms 6.438 MiB
#20 Accepted 1221ms 6.574 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;
}
//-------------------------辅助类函数-----------------------------
ll read(){
    ll num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if (c == '-')
        flag = true;
    else
        num = c - '0';
    while (isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * 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&&edgeq[rr].w>z){
             	addLine(x,y,z);
		   }
        }
    }
    return 0;
}

信息

递交者
类型
递交
题目
玩游戏(CQ直辖市noip模拟赛联考) T2
题目数据
下载
语言
C++
递交时间
2017-11-04 17:40:51
评测时间
2017-11-04 17:40:51
评测机
分数
100
总耗时
12455ms
峰值内存
6.832 MiB