제출 #689904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
689904		PoonYaPat	동기화 (JOI13_synchronization)	C++14	20 / 100	8087 ms	22980 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,m,q,val[100001],level[100001],p[100001][18],par[100001],line_val[100001];
pii line[200001];
vector<int> adj[100001];

void dfs(int x, int parent) {
    level[x]=level[parent]+1;
    p[x][0]=parent;
    for (int i=1; i<18; ++i) p[x][i]=p[p[x][i-1]][i-1];

    for (auto s : adj[x]) {
        if (s==parent) continue;
        dfs(s,x);
    }
}

int find(int x) { //find leader of group --> (wrong)
    while (par[x]==p[x][0]) x=p[x][0];
    return x;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>q;
    for (int i=1; i<=n-1; ++i) {
        cin>>line[i].first>>line[i].second;
        adj[line[i].first].push_back(line[i].second);
        adj[line[i].second].push_back(line[i].first);
    }
    for (int i=1; i<=n; ++i) par[i]=i, val[i]=1;
    dfs(1,0);

    while (m--) {
        int x; cin>>x;
        int a=line[x].first, b=line[x].second;
        if (level[a]>level[b]) swap(a,b);

        if (par[b]==a) { //line will disconnect
            line_val[x]=val[b]=val[find(a)];
            par[b]=b;
        } else { //line will connect
            par[b]=a;
            val[find(a)]=val[find(a)]+val[b]-line_val[x];
        }
    }

    while (q--) {
        int x; cin>>x;
        cout<<val[find(x)]<<"\n";
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 10 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40