Submission #888839

#	Time	Username	Problem	Language	Result	Execution time	Memory
888839		ByeWorld	Synchronization (JOI13_synchronization)	C++14	30 / 100	112 ms	262144 KiB

synchronization

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
//#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 1e5+20;
const int MAXA = 2e5+10;
const int LOG = 19;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
 
int n, m, q;
int u[MAXN], v[MAXN];
vector <int> adj[MAXN];
int par[MAXN], sub[MAXN], dep[MAXN], idx[MAXN];
int root[MAXN];
vector <int> ch[MAXN]; //isi chain
int ty[MAXA];

struct node {
    int bit[2*MAXN];

    // que
    int que(int x){ // mulai dari idx dep[x], cari ke atas yg duluan 1
        int dp = dep[x];
        int te = 0; // value suffix
        for(int i=dp; i>=1; i-=i&(-i)) te += bit[i];
        //cout << te << ' ' << x << " te\n";
        if(te==0) return -1; // gk ketemu
        //cout << " pp\n";
        // skrg cari te-1
        int ret = 0, sum = 0;
        for(int i=LOG-1; i>=0; i--){
            if(ret + (1<<i) <= 2*MAXN-10 && sum+bit[ret+(1<<i)] <= te-1){
                sum += bit[ret+(1<<i)];
                ret += (1<<i);
            }
        }

        // ret+1 --> depth dr yg valnya 1
        int ids = ret+1 - dep[root[x]]; // ids dari ch
        //cout << ids << " ids\n";
        return ch[root[x]][ids]; // idx yg valuenya 1
    }
    // upd
    void upd(int x, int y){ // depth dr idx = x
        for(int i=x; i<=2*MAXN-10; i+=i&(-i)) bit[i] += y;
    }
} *st[MAXN];

int query(int x){ // x --> idx nya
    while(st[x]->que(x) == -1){
        if(x==0) assert(false);

        x = par[root[x]];
    }
    // udh ketemu
    return st[x]->que(x); // idxnya
}
void update(int x, int nw){ // idx x += nw
    st[x]->upd(dep[x], nw);
}

void dfs(int nw, int pa){
    par[nw] = pa; sub[nw] = 1; dep[nw] = dep[pa]+1;
    for(auto nx : adj[nw]){
        if(nx == pa) continue;
        dfs(nx, nw);
        sub[nw] += sub[nx];
    }
}
void build(int x, int y){
    st[x] = new node();
    for(int i=dep[x]+1; i<=dep[y]; i++) st[idx[i]] = st[x];
}
int val[MAXN], up[MAXN];

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i=1; i<=n-1; i++){
        cin >> u[i] >> v[i];
        adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]);
    }
    dfs(1, 0);
    for(int i=1; i<=n-1; i++){
        if(dep[u[i]] > dep[v[i]]) swap(u[i], v[i]);
    }

    queue<int> qu; qu.push(1);
    while(!qu.empty()){
        int nw = qu.front(); int tp = nw; qu.pop();
        while(true){
            ch[tp].pb(nw);
            root[nw] = tp;
            idx[dep[nw]] = nw;
            
            int big = n+1;
            for(auto nx : adj[nw]){
                if(nx==par[nw]) continue;
                if(sub[nx] > sub[big]) big = nx;
            }
            if(big==n+1) break;
            for(auto nx : adj[nw]){
                if(nx==par[nw] || nx==big) continue;
                qu.push(nx);
            }
            
            nw = big;
        }
        build(tp, nw);
        if(qu.size() > n) assert(false);
    }

    int ins = 0;
    for(int i=1; i<=n; i++) ins += ch[i].size();
    if(ins > n) assert(false);

    for(int i=1; i<=n; i++){
        update(i, 1); 
        val[i] = 1; up[i] = 0;
    }

    for(int i=1; i<=m; i++){
        int x; cin >> x;
        //cout << u[x] << ' ' << v[x] << " atas\n";
        ty[x] = 1-ty[x];
        if(ty[x]){ // ke nyala, join
            update(v[x], -1); //yg bawah
            int idx = query(u[x]);
            val[idx] = val[idx]+val[v[x]]-up[v[x]];
        } else { // ke mati
            int idx = query(v[x]);
            //cout << i << ' ' << x << ' ' << idx << " idx\n";
            update(v[x], 1);
            val[v[x]] = val[idx];
            up[v[x]] = val[idx];
        }
        // for(int j=1; j<=n; j++){
        //     cout << j << ' '<< val[j] << ' ' << up[j] << " up\n";
        // }
    }

    while(q--){
        int x; cin >> x;
        int anc = query(x);
        cout << val[anc] << '\n';
        //cout << anc << ' ' << " anc\n";
    }
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:120:22: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |         if(qu.size() > n) assert(false);
      |            ~~~~~~~~~~^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40