Submission #640365

#	Time	Username	Problem	Language	Result	Execution time	Memory
640365		MohamedFaresNebili	Synchronization (JOI13_synchronization)	C++14	100 / 100	852 ms	25292 KiB

synchronization

#include <bits/stdc++.h>
///#pragma GCC optimize("O3,unroll-loops")
///#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

                    using namespace std;

                    const int LOG = 17;

                    int N, M, Q;
                    int timer, tin[100005], out[100005];
                    int res[100005], ST[400005], C[400005];
                    int P[100005][20], X[100005], Y[100005];
                    vector<int> adj[100005];
                    int state[100005];

                    void update(int v, int l, int r, int p, int val) {
                        if(l == r) {
                            ST[v] += val; return;
                        }
                        int md = (l + r) / 2;
                        if(p <= md) update(v * 2, l, md, p, val);
                        else update(v * 2 + 1, md + 1, r, p, val);
                        ST[v] = ST[v * 2] + ST[v * 2 + 1];
                    }
                    int query(int v, int l, int r, int lo, int hi) {
                        if(l > hi || r < lo) return 0;
                        if(l >= lo && r <= hi) return ST[v];
                        return query(v * 2, l, (l + r) / 2, lo, hi)
                            + query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
                    }

                    void dfs(int v, int p) {
                        tin[v] = timer++; P[v][0] = p;
                        for(auto u : adj[v]) {
                            if(u == p) continue;
                            dfs(u, v);
                        }
                        out[v] = timer;
                    }

                    int findSet(int v) {
                        int K = query(1, 0, N, 0, tin[v]);
                        for(int l = LOG - 1; ~l; l--)
                            if(P[v][l] != -1 && query(1, 0, N, 0, tin[P[v][l]]) == K)
                                v = P[v][l];
                        return v;
                    }

                    int32_t main() {
                        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                        cin >> N >> M >> Q;
                        for(int l = 1; l <= N - 1; l++) {
                            cin >> X[l] >> Y[l];
                            adj[X[l]].push_back(Y[l]);
                            adj[Y[l]].push_back(X[l]);
                        }

                        dfs(1, 1);

                        for(int l = 1; l < LOG; l++)
                            for(int i = 1; i <= N; i++)
                                P[i][l] = P[P[i][l - 1]][l - 1];

                        for(int l = 1; l <= N; l++) {
                            update(1, 0, N, tin[l], -1);
                            update(1, 0, N, out[l], 1);
                            res[l] = 1;
                        }

                        for(int l = 1; l <= M; l++) {
                            int D; cin >> D;
                            int U = X[D], V = Y[D];
                            if(P[U][0] == V) swap(U, V);

                            U = findSet(U);

                            if(state[D]) {
                                res[V] = C[V] = res[U];
                                update(1, 0, N, tin[V], -1);
                                update(1, 0, N, out[V], 1);
                            }
                            else {
                                res[U] += res[V] - C[V];
                                update(1, 0, N, tin[V], 1);
                                update(1, 0, N, out[V], -1);
                            }

                            state[D] = !state[D];
                        }

                        for(int l = 1; l <= Q; l++) {
                            int K; cin >> K;
                            cout << res[findSet(K)] << "\n";
                        }
                        return 0;
                    }

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