oj.uz

Submission #499575

# Submission time Handle Problem Language Result Execution time Memory
499575 2021-12-28T19:52:13 Z couplefire Synchronization (JOI13_synchronization) C++17
100 / 100
 268 ms 24176 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n, m, q, uu[N], vv[N], bit[N], lst[N], ans[N];
vector<int> adj[N];
int up[N][20], tin[N], tout[N], tid;

void upd(int pos, int val){
    for(; pos<N; pos=pos|(pos+1))
        bit[pos] += val;
}

int query(int pos){
    int res = 0;
    for(; pos>=0; pos=(pos&(pos+1))-1)
        res += bit[pos];
    return res;
}

void dfs(int v, int p){
    tin[v] = tid++;
    up[v][0] = p;
    for(int i = 1; i<20; ++i)
        up[v][i] = up[v][i-1]==-1?-1:up[up[v][i-1]][i-1];
    for(auto u : adj[v])
        if(u!=p) dfs(u, v);
    tout[v] = tid;
}

int get(int v){
    int a = query(tin[v]), b = v;
    for(int i = 19; i>=0; --i)
        if(up[b][i]!=-1 && query(tin[up[b][i]])==a)
            b = up[b][i];
    return b;
}

int main(){
    // freopen("a.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i = 0; i<n-1; ++i){
        cin >> uu[i] >> vv[i]; --uu[i], --vv[i];
        adj[uu[i]].push_back(vv[i]);
        adj[vv[i]].push_back(uu[i]);
    }
    dfs(0, -1);
    for(int i = 0; i<n-1; ++i)
        if(up[uu[i]][0]==vv[i])
            swap(uu[i], vv[i]);
    for(int i = 0; i<n; ++i)
        upd(tin[i], 1), upd(tout[i], -1), ans[i] = 1;
    for(int i = 0; i<m; ++i){
        int id; cin >> id; --id;
        int u = uu[id], v = vv[id];
        u = get(u);
        if(lst[id]==-1){
            upd(tin[v], 1); upd(tout[v], -1);
            lst[id] = ans[v] = ans[u];
        } else{
            upd(tin[v], -1); upd(tout[v], 1);
            int tmp = ans[u]+ans[v]-lst[id];
            ans[u] = ans[v] = tmp; lst[id] = -1;
        }
    }
    while(q--){
        int v; cin >> v; --v;
        cout << ans[get(v)] << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2672 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 11 ms 4292 KB Output is correct
8 Correct 11 ms 4172 KB Output is correct
9 Correct 13 ms 4300 KB Output is correct
10 Correct 171 ms 18732 KB Output is correct
11 Correct 144 ms 18760 KB Output is correct
12 Correct 220 ms 23280 KB Output is correct
13 Correct 67 ms 18568 KB Output is correct
14 Correct 126 ms 18168 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 20880 KB Output is correct
2 Correct 71 ms 20720 KB Output is correct
3 Correct 105 ms 22724 KB Output is correct
4 Correct 91 ms 22768 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2664 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 20 ms 4776 KB Output is correct
8 Correct 265 ms 24092 KB Output is correct
9 Correct 268 ms 24176 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 24108 KB Output is correct
2 Correct 158 ms 23724 KB Output is correct
3 Correct 140 ms 23876 KB Output is correct
4 Correct 146 ms 24012 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2884 KB Output is correct
6 Correct 14 ms 4352 KB Output is correct
7 Correct 176 ms 19760 KB Output is correct
8 Correct 265 ms 24092 KB Output is correct
9 Correct 78 ms 19684 KB Output is correct
10 Correct 123 ms 19448 KB Output is correct
11 Correct 113 ms 22036 KB Output is correct
12 Correct 98 ms 22004 KB Output is correct
13 Correct 140 ms 23936 KB Output is correct