oj.uz

Submission #843939

# Submission time Handle Problem Language Result Execution time Memory
843939 2023-09-04T17:38:35 Z vjudge1 Synchronization (JOI13_synchronization) C++17
100 / 100
 186 ms 21844 KB 
#include <bits/stdc++.h>
using namespace std;

/// 123
const int MAXN = 1e5 + 1;
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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 2 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 6 ms 5724 KB Output is correct
8 Correct 7 ms 5724 KB Output is correct
9 Correct 6 ms 5724 KB Output is correct
10 Correct 70 ms 10984 KB Output is correct
11 Correct 92 ms 11088 KB Output is correct
12 Correct 115 ms 18680 KB Output is correct
13 Correct 40 ms 11408 KB Output is correct
14 Correct 51 ms 12804 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 14940 KB Output is correct
2 Correct 54 ms 17044 KB Output is correct
3 Correct 69 ms 20560 KB Output is correct
4 Correct 81 ms 20308 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5208 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 13 ms 6664 KB Output is correct
8 Correct 157 ms 18844 KB Output is correct
9 Correct 160 ms 19024 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 19100 KB Output is correct
2 Correct 114 ms 19280 KB Output is correct
3 Correct 115 ms 19292 KB Output is correct
4 Correct 113 ms 19284 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory 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 5212 KB Output is correct
6 Correct 8 ms 5724 KB Output is correct
7 Correct 90 ms 11364 KB Output is correct
8 Correct 160 ms 21844 KB Output is correct
9 Correct 61 ms 14416 KB Output is correct
10 Correct 78 ms 14104 KB Output is correct
11 Correct 78 ms 18260 KB Output is correct
12 Correct 77 ms 18208 KB Output is correct
13 Correct 116 ms 21668 KB Output is correct