Submission #843478

#	Time	Username	Problem	Language	Result	Execution time	Memory
843478		Cookie	Synchronization (JOI13_synchronization)	C++14	100 / 100	196 ms	22584 KiB

synchronization

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int base = 74;
const int mxn = 1e5 + 5;
const ll inf = 1e18;
int n, m, q;
vt<int>adj[mxn + 1];
int dep[mxn + 1], tin[mxn + 1], tout[mxn + 1], ans[mxn + 1], tt = 0;
bool on[mxn + 1];
int bit[mxn + 1], up[mxn + 1][18], u[mxn + 1], v[mxn + 1], last[mxn + 1];
void upd(int p, int v){
    while(p <= n + 1){
        bit[p] += v; p += p & (-p);
    }
}
int get(int p){
    int ans = 0;
    while(p){
        ans += bit[p]; p -= p & (-p);
    }
    return(ans);
}
void dfs(int s, int pre){
    tin[s] = ++tt;
    for(auto i: adj[s]){
        if(i != pre){
            up[i][0] = s; dep[i] = dep[s] + 1;
            dfs(i, s);
        }
    }
    tout[s] = tt;
}
int get_root(int u){
    int ans = u;
    for(int i = 17; i >= 0; i--){
        if(up[ans][i] != 0 && get(tin[up[ans][i]]) == get(tin[u])){
            ans = up[ans][i];
        }
    }
    return(ans);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        cin >> u[i] >> v[i];
        adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]);
    }
    dfs(1, -1);
    for(int i = 1; i < 18; i++){
        for(int j = 1; j <= n; j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    for(int i = 1; i <= n; i++){
        ans[i] = 1;
        if(i != 1){
            upd(tin[i], 1); upd(tout[i] + 1, -1);
        }
    }
    for(int i = 0; i < m; i++){
        int id; cin >> id;
        int nodeu = u[id], nodev = v[id];
        if(dep[nodeu] > dep[nodev])swap(nodeu, nodev);
        if(!on[id]){
            int rootu = get_root(nodeu);
            ans[rootu] += ans[nodev] - last[nodev];
            upd(tin[nodev], -1); upd(tout[nodev] + 1, 1);
        }else{
            ans[nodev] = last[nodev] = ans[get_root(nodeu)];
            upd(tin[nodev], 1); upd(tout[nodev] + 1, -1);
        }
        on[id] = !on[id];
    }
   
    while(q--){
        int x; cin >> x;
        cout << ans[get_root(x)] << "\n";
    }
    return(0);
}

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