oj.uz

Submission #171423

# Submission time Handle Problem Language Result Execution time Memory
171423 2019-12-28T16:08:48 Z dolphingarlic Synchronization (JOI13_synchronization) C++14
100 / 100
 987 ms 23936 KB 
#include <bits/stdc++.h>
#define FOR(i,x,y)for(int i = x; i < y; i++)
#define x first
#define y second
using namespace std;
const int N = 200001;
vector<int> g[N];
pair<int,int> e[N];
int n,m,q,f[N],l[N],t = 1,tin[N],tout[N],c[N][20],b[N];
void dfs(int v = 1,int p = 0){
    c[v][0] = p;
    FOR(i,1,20)c[v][i] = c[c[v][i - 1]][i - 1];
    f[v] = 1;
    tin[v] = t++;
    for(int i : g[v])if(i != p)dfs(i,v);
    tout[v] = t;
}
void up(int p,int val){ for(; p <= n; p +=(p &(-p)))b[p] += val; }
int qu(int p){
    int ans = 0;
    for(; p; p -=(p &(-p)))ans += b[p];
    return ans;
}
int lca(int v){
    int ll = v;
    for(int i = 19; ~i; i--)if(c[ll][i] && qu(tin[c[ll][i]])== qu(tin[v]))ll = c[ll][i];
    return ll;
}
main(){
    cin >> n >> m >> q;
    FOR(i,1,n){
        cin >> e[i].x >> e[i].y;
        g[e[i].x].push_back(e[i].y);
        g[e[i].y].push_back(e[i].x);
    }
    dfs();
    FOR(i,1,n + 1){
        up(tin[i],-1);
        up(tout[i],1);
    }
    while(m--){
        int x;
        cin >> x;
        int u = e[x].x,v = e[x].y;
        if(c[u][0] == v)swap(u,v);
        if(lca(v)!= v){
            f[v] = l[v] = f[lca(u)];
            up(tin[v],-1);
            up(tout[v],1);
        } else {
            f[lca(u)] += f[v] - l[v];
            up(tin[v],1);
            up(tout[v],-1);
        }
    }
    while(q--){
        int x;
        cin >> x;
        cout << f[lca(x)] << '\n';
    }
}

Compilation message

synchronization.cpp:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5100 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5084 KB Output is correct
5 Correct 6 ms 5080 KB Output is correct
6 Correct 9 ms 5240 KB Output is correct
7 Correct 38 ms 6396 KB Output is correct
8 Correct 40 ms 6520 KB Output is correct
9 Correct 39 ms 6392 KB Output is correct
10 Correct 584 ms 18916 KB Output is correct
11 Correct 540 ms 19008 KB Output is correct
12 Correct 611 ms 23496 KB Output is correct
13 Correct 319 ms 19184 KB Output is correct
14 Correct 349 ms 18480 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 20956 KB Output is correct
2 Correct 294 ms 20856 KB Output is correct
3 Correct 282 ms 23160 KB Output is correct
4 Correct 284 ms 23148 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 12 ms 5240 KB Output is correct
7 Correct 78 ms 6988 KB Output is correct
8 Correct 933 ms 23868 KB Output is correct
9 Correct 946 ms 23892 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 953 ms 23796 KB Output is correct
2 Correct 647 ms 23800 KB Output is correct
3 Correct 647 ms 23800 KB Output is correct
4 Correct 649 ms 23800 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4980 KB Output is correct
2 Correct 6 ms 4988 KB Output is correct
3 Correct 7 ms 4984 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 12 ms 5116 KB Output is correct
6 Correct 73 ms 6476 KB Output is correct
7 Correct 902 ms 19288 KB Output is correct
8 Correct 987 ms 23936 KB Output is correct
9 Correct 694 ms 19824 KB Output is correct
10 Correct 677 ms 19320 KB Output is correct
11 Correct 644 ms 21744 KB Output is correct
12 Correct 634 ms 21752 KB Output is correct
13 Correct 650 ms 23928 KB Output is correct