Submission #689899

#	Time	Username	Problem	Language	Result	Execution time	Memory
689899		PoonYaPat	Synchronization (JOI13_synchronization)	C++14	0 / 100	142 ms	22948 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
    if (par[x]!=p[x][0]) return x;
    for (int i=17; i>=0; --i) {
        if (par[p[x][i]]==p[p[x][i]][0] && p[x][i]!=0) x=p[x][i];
    }
    return p[x][0];
}

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[a]+val[b]-line_val[x];
        }
    }

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

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