oj.uz

Submission #479228

# Submission time Handle Problem Language Result Execution time Memory
479228 2021-10-10T23:02:35 Z bonopo Synchronization (JOI13_synchronization) C++17
0 / 100
 950 ms 24088 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 up(int u, int k) {
    for(int i=LOG-1; i>=0; --i) if(k>=(1<<i)) u=pa[i][u], k-=1<<i;
    return u;
}

int rt(int u) {
    int lo=0, hi=N, mid, ret=u;
    while(lo<=hi) {
        mid=lo+hi>>1; int nx=up(u, mid);
        if(qry(in[u])-qry(in[nx])==mid) ret=nx, lo=mid+1;
        else hi=mid-1;
    }
    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, 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

Compilation message

synchronization.cpp: In function 'int rt(int)':
synchronization.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         mid=lo+hi>>1; int nx=up(u, mid);
      |             ~~^~~

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 246 ms 20420 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 2796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 950 ms 24088 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 2796 KB Output is correct
2 Incorrect 2 ms 2764 KB Output isn't correct
3 Halted 0 ms 0 KB -