Submission #198852

#	Time	Username	Problem	Language	Result	Execution time	Memory
198852		osaaateiasavtnl	Synchronization (JOI13_synchronization)	C++14	100 / 100	375 ms	24440 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 2e5 + 7;
int n, m, q;
vector <int> g[N];
ii ed[N];
int tin[N], tout[N], ptr = 0, par[N], num[N];
void dfs(int u, int p) {
    par[u] = p;
    tin[u] = ++ptr;
    num[ptr] = u;
    for (int v : g[u]) 
        if (v != p)
            dfs(v, u);
    tout[u] = ptr;
}
int r[N << 2];
void upd(int v, int tl, int tr, int i, int x) {
    if (tl == tr) {
        r[v] = x;
        return;
    }
    int tm = (tl + tr) >> 1;
    if (i <= tm)
        upd(v * 2 + 1, tl, tm, i, x);
    else
        upd(v * 2 + 2, tm + 1, tr, i, x);
    r[v] = max(r[v * 2 + 1], r[v * 2 + 2]);
}   
int get(int v, int tl, int tr, int i) {
    if (i < tl || r[v] < i)
        return -1;
    if (tl == tr)
        return num[tl];
    int tm = (tl + tr) >> 1;
    int t = get(v * 2 + 2, tm + 1, tr, i);
    if (t != -1)
        return t;
    else
        return get(v * 2 + 1, tl, tm, i);
}   
int rep(int u) {
    return get(0, 1, n, tin[u]);        
}
int ans[N], last[N];
int get(int u) {
    return ans[rep(u)];
}   
bool cur[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m >> q;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        ed[i] = mp(u, v);
        g[u].app(v); g[v].app(u);
    }   
    dfs(1, 1);
    for (int i = 0; i < n - 1; ++i) 
        if (par[ed[i].s] == ed[i].f)
            swap(ed[i].f, ed[i].s);
    for (int i = 1; i <= n; ++i)
        upd(0, 1, n, tin[i], tout[i]);
    for (int i = 1; i <= n; ++i)
        ans[i] = 1;
    while (m--) {
        int i;
        cin >> i;
        --i;
        #ifdef HOME
        cout << i + 1 << " : " << rep(ed[i].f) << ' ' << rep(ed[i].s) << '\n';
        #endif
        if (!cur[i]) {
            ans[rep(ed[i].s)] = ans[rep(ed[i].s)] + ans[rep(ed[i].f)] - last[i];
            upd(0, 1, n, tin[ed[i].f], -1);
        }
        else {
            last[i] = ans[ed[i].f] = get(ed[i].f);
            upd(0, 1, n, tin[ed[i].f], tout[ed[i].f]);
        }
        cur[i] ^= 1;
    }   
    while (q--) {
        int u; cin >> u;
        cout << get(u) << '\n';
    }    
}   

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