oj.uz

답안 #640365

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
640365 2022-09-14T11:08:45 Z MohamedFaresNebili 동기화 (JOI13_synchronization) C++14
100 / 100
 852 ms 25292 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2728 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 5 ms 2876 KB Output is correct
7 Correct 41 ms 4408 KB Output is correct
8 Correct 43 ms 4324 KB Output is correct
9 Correct 40 ms 4308 KB Output is correct
10 Correct 510 ms 19860 KB Output is correct
11 Correct 555 ms 19804 KB Output is correct
12 Correct 674 ms 24372 KB Output is correct
13 Correct 488 ms 19704 KB Output is correct
14 Correct 346 ms 18760 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 367 ms 21684 KB Output is correct
2 Correct 359 ms 21456 KB Output is correct
3 Correct 268 ms 23636 KB Output is correct
4 Correct 277 ms 23372 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 6 ms 2824 KB Output is correct
7 Correct 61 ms 4912 KB Output is correct
8 Correct 852 ms 25172 KB Output is correct
9 Correct 825 ms 25284 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 845 ms 25284 KB Output is correct
2 Correct 465 ms 24516 KB Output is correct
3 Correct 485 ms 24604 KB Output is correct
4 Correct 464 ms 24600 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 5 ms 2772 KB Output is correct
6 Correct 55 ms 4448 KB Output is correct
7 Correct 690 ms 20660 KB Output is correct
8 Correct 821 ms 25292 KB Output is correct
9 Correct 551 ms 20732 KB Output is correct
10 Correct 473 ms 20116 KB Output is correct
11 Correct 507 ms 22924 KB Output is correct
12 Correct 513 ms 22844 KB Output is correct
13 Correct 479 ms 24592 KB Output is correct