oj.uz

Submission #479229

# Submission time Handle Problem Language Result Execution time Memory
479229 2021-10-10T23:09:20 Z bonopo Synchronization (JOI13_synchronization) C++17
0 / 100
 524 ms 21224 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<2*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) {
    for(int i=LOG-1, k=0; i>=0; --i) if(qry(in[u])-qry(in[pa[i][u]])==k+(1<<i)) {
        k+=1<<i; u=pa[i][u]; }
    return u;
}

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, x; i<=M; ++i) {
        cin>>x;

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

        if(st[x]) {
            // turn edge off
            upd(in[v], -1); upd(ot[v],  1);
            u=rt(u); c[v]=l[u]=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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 18404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 524 ms 21224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Incorrect 2 ms 2764 KB Output isn't correct
3 Halted 0 ms 0 KB -