oj.uz

답안 #843938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843938 2023-09-04T17:35:54 Z vjudge1 동기화 (JOI13_synchronization) C++17
30 / 100
 172 ms 21072 KB 
#include <bits/stdc++.h>
using namespace std;

/// 123
const int MAXN = 1e5;
vector<int> adj[MAXN];
int f[MAXN];
int nxt[MAXN];
int par[MAXN];
pair<int, int> edge[MAXN];
#define time tme
int time = 1;
int last[MAXN];
int ans[MAXN];
int active[MAXN];
int tin[MAXN], out[MAXN];
int d[MAXN], rev[MAXN];

void prep(int u, int p) {
}

void dfs(int u, int p) {
        par[u] = p;
        f[u] = 1;
        for (int i = 0; i < adj[u].size(); i++) {
                if (adj[u][i] == p) {
                        swap(adj[u][i], adj[u].back());
                        adj[u].pop_back();
                        break;
                }
        }
        for (int& v : adj[u]) {
                d[v] = d[u] + 1;
                dfs(v, u);
                f[u] += f[v];
                if (f[v] > f[adj[u][0]]) swap(v, adj[u][0]);
        }
}

void hld(int u) {
        rev[time] = u;
        tin[u] = time++;
        for (int v : adj[u]) {
                nxt[v] = v == adj[u][0] ? nxt[u] : v;
                hld(v);
        }
        out[u] = time;
}

template <class T>
class fenwick_t {
       public:
        vector<T> bit;
        int n;

        fenwick_t(int n = 0) : n(n) {
                bit.resize(n + 1, 0);
        }

        void Update(int pos, T val) {
                for (; pos <= n; pos += pos & -pos) {
                        bit[pos] += val;
                }
        }

        T Get(int pos) {
                T res = T(0);
                for (; pos > 0; pos -= pos & -pos) {
                        res += bit[pos];
                }
                return res;
        }

        T Get(int l, int r) {
                return Get(r) - (l ? Get(l - 1) : T(0));
        }
};

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n, m, q;
        cin >> n >> m >> q;
        for (int i = 0; i < n - 1; i++) {
                int u, v;
                cin >> u >> v;
                u--, v--;
                adj[u].emplace_back(v);
                adj[v].emplace_back(u);
                edge[i] = {u, v};
        }

        prep(0, -1);
        dfs(0, -1);
        hld(0);

        for (int i = 0; i < n - 1; i++) {
                if (d[edge[i].first] < d[edge[i].second]) {
                        swap(edge[i].first, edge[i].second);
                }
        }
        for (int i = 0; i < n; i++) ans[i] = 1;
        fenwick_t<int> fw(n);
        auto root = [&](int x) {
                while (true) {
                        if (fw.Get(tin[nxt[x]], tin[x]) != tin[x] - tin[nxt[x]] + 1) {
                                int l = tin[nxt[x]], r = tin[x], res = -1;
                                while (l <= r) {
                                        int mid = l + r >> 1;
                                        if (fw.Get(mid, tin[x]) != tin[x] - mid + 1) {
                                                res = rev[mid];
                                                l = mid + 1;
                                        } else {
                                                r = mid - 1;
                                        }
                                }
                                return assert(res != -1), res;
                        } else {
                                x = par[nxt[x]];
                        }
                }
        };

        while (m--) {
                int e;
                cin >> e;
                e--;
                auto [x, y] = edge[e];
                //   y
                //   |
                //   x
                int r = root(y);
                active[e] ^= 1;
                if (active[e]) {
                        ans[x] = ans[r] = ans[r] + ans[x] - last[e];
                        fw.Update(tin[x], +1);
                } else {
                        ans[x] = last[e] = ans[r];
                        fw.Update(tin[x], -1);
                }
        }
        while (q--) {
                int u;
                cin >> u;
                u--;
                cout << ans[root(u)] << '\n';
        }
}

Compilation message

synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (int i = 0; i < adj[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
synchronization.cpp: In lambda function:
synchronization.cpp:109:53: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |                                         int mid = l + r >> 1;
      |                                                   ~~^~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 5464 KB Output is correct
3 Correct 2 ms 5304 KB Output is correct
4 Correct 1 ms 5468 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 6 ms 5980 KB Output is correct
8 Correct 7 ms 5980 KB Output is correct
9 Correct 7 ms 6096 KB Output is correct
10 Correct 80 ms 13352 KB Output is correct
11 Correct 81 ms 13288 KB Output is correct
12 Correct 118 ms 21072 KB Output is correct
13 Incorrect 50 ms 13256 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 15008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 14 ms 6684 KB Output is correct
8 Correct 170 ms 18836 KB Output is correct
9 Correct 169 ms 19024 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 19028 KB Output is correct
2 Correct 113 ms 19252 KB Output is correct
3 Correct 118 ms 19536 KB Output is correct
4 Correct 112 ms 19284 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 5212 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 2 ms 5308 KB Output is correct
6 Correct 8 ms 6056 KB Output is correct
7 Incorrect 115 ms 14056 KB Output isn't correct
8 Halted 0 ms 0 KB -