oj.uz

Submission #1079415

# Submission time Handle Problem Language Result Execution time Memory
1079415 2024-08-28T14:16:48 Z Hamed_Ghaffari Synchronization (JOI13_synchronization) C++17
100 / 100
 220 ms 24400 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back

const int MXN = 1e5+5;
const int LOG = 17;

int fen[MXN];
inline void updx(int p, int x) {
    for(p+=2; p<MXN; p+=p&-p) fen[p] += x;
}
inline int getx(int p) {
    int res=0;
    for(p+=2; p; p-=p&-p) res += fen[p];
    return res;
}

int n, m, q, par[LOG][MXN], E[MXN], ans[MXN], lst[MXN];
bool on[MXN];
vector<int> g[MXN];
int stt[MXN], fnt[MXN], timer;

void dfs(int v) {
    ans[v] = 1;
    stt[v] = ++timer;
    for(int i=1; i<LOG; i++) par[i][v] = par[i-1][par[i-1][v]];
    for(int i : g[v])
        if((E[i]^v) == par[0][v]) E[i] = v;
        else par[0][E[i]^v]=v, dfs(E[i]^v);
    fnt[v] = timer+1;
    if(par[0][v]) updx(stt[v], 1), updx(fnt[v], -1);
}

int get_root(int v) {
    for(int i=LOG-1; i>=0; i--)
        if(par[i][v] && getx(stt[par[i][v]])==getx(stt[v]))
            v = par[i][v];
    return v;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i=1,u,v; i<n; i++) {
        cin >> u >> v;
        E[i] = u^v;
        g[u].pb(i);
        g[v].pb(i);
    }
    dfs(1);
    while(m--) {
        int v;
        cin >> v; v = E[v];
        if(on[v]) {
            ans[v] = lst[v] = ans[get_root(v)];
            updx(stt[v], 1); updx(fnt[v], -1);
        }
        else {
            updx(stt[v], -1); updx(fnt[v], 1);
            ans[get_root(v)] += ans[v]-lst[v];
        }
        on[v] ^= 1;
    }
    while(q--) {
        int v;
        cin >> v;
        cout << ans[get_root(v)] << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 2 ms 2908 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 2720 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 9 ms 4136 KB Output is correct
8 Correct 10 ms 4188 KB Output is correct
9 Correct 10 ms 4188 KB Output is correct
10 Correct 130 ms 17284 KB Output is correct
11 Correct 136 ms 17232 KB Output is correct
12 Correct 170 ms 23376 KB Output is correct
13 Correct 74 ms 17328 KB Output is correct
14 Correct 92 ms 16412 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 20052 KB Output is correct
2 Correct 61 ms 19792 KB Output is correct
3 Correct 75 ms 22608 KB Output is correct
4 Correct 70 ms 22612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 2 ms 2828 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 15 ms 4956 KB Output is correct
8 Correct 220 ms 24148 KB Output is correct
9 Correct 212 ms 24252 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 24144 KB Output is correct
2 Correct 109 ms 23636 KB Output is correct
3 Correct 119 ms 23632 KB Output is correct
4 Correct 108 ms 23636 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 2 ms 2952 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2904 KB Output is correct
6 Correct 12 ms 4444 KB Output is correct
7 Correct 155 ms 18096 KB Output is correct
8 Correct 210 ms 24400 KB Output is correct
9 Correct 79 ms 18356 KB Output is correct
10 Correct 104 ms 17748 KB Output is correct
11 Correct 79 ms 21196 KB Output is correct
12 Correct 83 ms 21264 KB Output is correct
13 Correct 109 ms 23632 KB Output is correct