Submission #597523

#	Time	Username	Problem	Language	Result	Execution time	Memory
597523		AA_Surely	Synchronization (JOI13_synchronization)	C++17	50 / 100	8058 ms	22312 KiB

synchronization

#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define pb push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()


using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;

#define lc now << 1
#define rc now << 1 | 1

int n, m, q, t[N], cnt;
int par[N], ans[N], mem[N], sz[N], head[N];
bool exist[N];
PII eset[N];
VPII adj[N];
VI order;

struct SegTree {
    int seg[N << 2];

    void change(int id, int val, int now = 1, int ls = 0, int rs = n - 1) {
        if (ls == rs) {
            seg[now] = val;
            return;
        }

        int mid = (ls + rs) >> 1;
        if (id <= mid) change(id, val, lc, ls, mid);
        else change(id, val, rc, mid + 1, rs);

        seg[now] = seg[lc] + seg[rc];
        return;
    }

    int rightest(int rq, int now = 1, int ls = 0, int rs = n - 1) {
        //cout << "now on : " << ls << ' ' << rs << endl;
        if (ls > rq || seg[now] == (rs - ls + 1)) return -1;
        if (ls == rs) return ls;

        int mid = (ls + rs) >> 1;
        int case1 =  rightest(rq, rc, mid + 1, rs);
        return (case1 != -1 ? case1 : rightest(rq, lc, ls, mid));
    }
} tree;

void init() {
    cin >> n >> m >> q;
    F0R(i, n - 1) {
        int u, v; cin >> u >> v;
        adj[--u].pb({--v, i});
        adj[v].pb({u, i});
        eset[i] = {u, v};
    }

    return;
}

void preD(int now, int p) {
    t[now] = cnt++;
    order.pb(now);
    sz[now] = 1;
    par[now] = p;

    for(const auto &[on, id] : adj[now]) if (on != p) {
        preD(on, now);
        sz[now] += sz[on];
    }

    return;
}

void dfs(int now) {
    if (adj[now].size() >= 2) head[ adj[now][1].F ] = head[now];
    for(const auto &[on, id] : adj[now]) if (on != par[now]) {
        if (on == eset[id].F) swap(eset[id].F, eset[id].S);
        dfs(on);
    }
}

void rebuild() {
    preD(0, -1);
    F0R(i, n) sort(ALL(adj[i]), [](const PII &a, const PII &b){return sz[a.S] > sz[b.S];});
    iota(head, head + n, 0);

    dfs(0);

    fill(ans, ans + n, 1);

    return;
}

int grand(int v) {
    //cout << "now on : " << v + 1 << " with head " << head[v] << endl;
    int pl = tree.rightest(t[v]);
    //cout << "rightest is " << pl + 1 << endl;
    if (pl < t[ head[v] ]) return grand(par[ head[v] ]);
    return order[pl];
}

inline int get(int v) {
    return ans[ grand(v) ];
}

void rem(int x) {
    mem[x] = get(eset[x].F);
    tree.change(t[ eset[x].S ], 0);
    ans[ eset[x].S ] = mem[x];
    exist[x] = 0;
    return;
}

void add(int x) {
    int up = get(eset[x].F);
    int dn = ans[ eset[x].S ];

    int p = grand(eset[x].F);
    ans[p] = up + dn - mem[x];
    //cout << "ans[" << p + 1 << "] = " << ans[p] << endl;
    tree.change(t[ eset[x].S ], 1);
    //cout << "changing t[" << eset[x].S + 1 << "] to 1" << endl;

    exist[x] = 1;
    return;
}

int main() {
    IOS;

    init();
    rebuild();
    
    //F0R(i, n) cout << head[i] << ' '; cout << endl;

    while(m--) {
        int id; cin >> id; id--;
        if (exist[id]) rem(id);
        else add(id);
    }

    while(q--) {
        int v; cin >> v; v--;
        cout << get(v) << endl;
    }

    return 0;
}

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