oj.uz

Submission #689904

# Submission time Handle Problem Language Result Execution time Memory
689904 2023-01-29T17:39:58 Z PoonYaPat Synchronization (JOI13_synchronization) C++14
20 / 100
 8000 ms 22980 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2676 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2724 KB Output is correct
7 Correct 7 ms 4132 KB Output is correct
8 Correct 8 ms 4052 KB Output is correct
9 Correct 7 ms 4052 KB Output is correct
10 Correct 97 ms 17596 KB Output is correct
11 Correct 98 ms 17572 KB Output is correct
12 Correct 80 ms 22164 KB Output is correct
13 Correct 50 ms 17500 KB Output is correct
14 Correct 83 ms 16536 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8087 ms 17612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 9 ms 4612 KB Output is correct
8 Correct 94 ms 22980 KB Output is correct
9 Correct 101 ms 22924 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 20448 KB Output is correct
2 Execution timed out 8006 ms 21028 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 10 ms 4224 KB Output is correct
7 Correct 125 ms 18436 KB Output is correct
8 Correct 108 ms 22952 KB Output is correct
9 Correct 77 ms 18616 KB Output is correct
10 Correct 130 ms 17848 KB Output is correct
11 Execution timed out 8021 ms 18872 KB Time limit exceeded
12 Halted 0 ms 0 KB -