Submission #1282659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282659		daotuankhoi	Synchronization (JOI13_synchronization)	C++20	100 / 100	192 ms	22316 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; }

const int MAXN = 1e5 + 5, LG = 16;
vector<int> g[MAXN];
int up[MAXN][LG + 1], dep[MAXN], in[MAXN], out[MAXN], tour = 0;
pair<int, int> e[MAXN];
int bit[MAXN], n, m, q, res[MAXN], lst[MAXN];
bool sta[MAXN];

void add(int i, int v) {
    for (; i <= n; i += i & -i) bit[i] += v;
}

int get(int i) {
    int ans = 0;
    for (; i > 0; i -= i & -i) ans += bit[i];
    return ans;
}

void dfs(int u, int p) {
    in[u] = ++tour;
    for (int i = 1; i <= LG; i++) up[u][i] = up[up[u][i - 1]][i - 1];
    for (int v : g[u]) {
        if (v != p) {
            up[v][0] = u;
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
    }
    out[u] = tour;
}

int jump(int u) {
    for (int i = LG; i >= 0; i--) {
        if (up[u][i] && get(in[u]) - get(in[up[u][i]]) == (1 << i)) u = up[u][i];
    }
    return u;
}

int main() {
    #define NAME "test"
    if (fopen(NAME".inp", "r")) {
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        e[i] = {u, v};
    }
    dfs(1, 1);
    for (int i = 1; i <= n; i++) res[i] = 1;
    for (int i = 1; i < n; i++) {
        if (dep[e[i].fi] > dep[e[i].se]) swap(e[i].fi, e[i].se);
    }
    for (int i = 1; i <= m; i++) {
        int p; cin >> p;
        sta[p] ^= 1;
        auto [u, v] = e[p];
        if (sta[p]) {
            res[jump(u)] += res[v] - lst[p];
            res[u] = res[jump(u)];
            add(in[v], 1);
            add(out[v] + 1, -1);
        } else {
            res[u] = res[v] = lst[p] = res[jump(u)];
            add(in[v], -1);
            add(out[v] + 1, 1);
        }
    }
    for (int i = 1; i <= q; i++) {
        int x; cin >> x;
        cout << res[jump(x)] << ' ';
    }
    return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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