Submission #479230

#	Time	Username	Problem	Language	Result	Execution time	Memory
479230		bonopo	Synchronization (JOI13_synchronization)	C++17	0 / 100	915 ms	21164 KiB

synchronization

#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, 1);
    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 (stderr)

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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40