oj.uz

Submission #479236

# Submission time Handle Problem Language Result Execution time Memory
479236 2021-10-11T00:34:28 Z bonopo Synchronization (JOI13_synchronization) C++17
100 / 100
 490 ms 24224 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second

typedef long long ll;
const int MM=1e5+5, MOD=1e9+7, LOG=19;
int N, M, Q, pa[LOG][MM], bit[MM], st[MM], in[MM], ot[MM], c[MM], l[MM], dt;
pair<int,int> edg[MM];
vector<int> adj[MM];

void upd(int idx, int v) {
    for(; idx<MM; idx+=idx&-idx) bit[idx]+=v;
}

int qry(int idx) {
    int ret=0;
    for(; idx>=1; idx-=idx&-idx) ret+=bit[idx];
    return ret;
}

void dfs(int u, int fa) {
    pa[0][u]=fa; in[u]=++dt;
    for(int i=1; i<LOG; ++i) {
        pa[i][u]=pa[i-1][pa[i-1][u]]; }
    for(int &v:adj[u]) if(v!=fa) {
        dfs(v, u); }
    ot[u]=dt+1;
}

int rt(int u) {
    int ret=u;
    for(int i=LOG-1; i>=0; --i)
        if(pa[i][ret]&&qry(in[u])==qry(in[pa[i][ret]])) ret=pa[i][ret];
    return ret;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>N>>M>>Q;
    fill(c+1, c+N+1, 1);
    for(int i=1; i<N; ++i) {
        int u, v; cin>>u>>v;
        adj[u].pb(v), adj[v].pb(u);
        edg[i]={u,v};
    }

    dfs(1, 0);
    for(int i=1; i<N; ++i) {
        int u=edg[i].f, v=edg[i].s;
        if(in[u]>in[v]) swap(u, v);
        upd(in[v], -1);
        upd(ot[v],  1);
    }

    for(int i=1, x; i<=M; ++i) {
        cin>>x;

        int u=edg[x].f, v=edg[x].s;
        if(pa[0][u]==v) swap(u, v);

        if(st[x]) {
            // turn edge off
            upd(in[v], -1); upd(ot[v],  1);
            u=rt(u); c[v]=l[v]=c[u];
        } else {
            // turn edge on
            upd(in[v],  1); upd(ot[v], -1);
            u=rt(u); c[u]+=c[v]-l[v];
        }

        st[x]^=1;
    }

    for(int i=1, x; i<=Q; ++i) {
        cin>>x; x=rt(x);
        cout<<c[x]<<el;
    }
}

// MM

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2800 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2800 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 15 ms 4276 KB Output is correct
8 Correct 14 ms 4352 KB Output is correct
9 Correct 13 ms 4392 KB Output is correct
10 Correct 261 ms 18744 KB Output is correct
11 Correct 238 ms 18668 KB Output is correct
12 Correct 419 ms 23448 KB Output is correct
13 Correct 80 ms 18620 KB Output is correct
14 Correct 160 ms 17872 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 18628 KB Output is correct
2 Correct 91 ms 20400 KB Output is correct
3 Correct 113 ms 22340 KB Output is correct
4 Correct 109 ms 22388 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 4 ms 2892 KB Output is correct
7 Correct 29 ms 4880 KB Output is correct
8 Correct 483 ms 24224 KB Output is correct
9 Correct 490 ms 24132 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 21220 KB Output is correct
2 Correct 173 ms 23492 KB Output is correct
3 Correct 161 ms 23492 KB Output is correct
4 Correct 165 ms 23492 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 18 ms 4428 KB Output is correct
7 Correct 324 ms 19640 KB Output is correct
8 Correct 478 ms 24104 KB Output is correct
9 Correct 117 ms 19772 KB Output is correct
10 Correct 197 ms 19048 KB Output is correct
11 Correct 122 ms 21764 KB Output is correct
12 Correct 116 ms 21808 KB Output is correct
13 Correct 166 ms 23620 KB Output is correct