Submission #1279124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279124		Bui_Quoc_Cuong	Synchronization (JOI13_synchronization)	C++20	100 / 100	154 ms	18376 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int n, m, q;
vector <int> ke[N];
pair <int, int> edges[N];
int pos[N], heavy[N], sz[N], head[N], cur[N], timedfs, crt, h[N], par[N], arr[N];

int ans[N], last[N], state[N];

int st[4 * N];

void dfs (int u) {
	sz[u] = 1;
	for (int &v : ke[u]) if (v != par[u]) {
		par[v] = u;
		h[v] = h[u] + 1;
		dfs(v);
		sz[u]+= sz[v];
		if (sz[v] > sz[heavy[u]]) {
			heavy[u] = v;
		}
	}
}

void hld (int u) {
	if (!head[crt]) head[crt] = u;
	pos[u] = ++ timedfs;
	arr[pos[u]] = u;
	cur[u] = crt;

	if (heavy[u]) hld(heavy[u]);

	for (int &v : ke[u]) if (v != par[u] && v != heavy[u]) {
		crt++;
		hld(v);
	}
}

void update (int pos, int val) {
	int id = 1, l = 1, r = n;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (pos <= mid) id = id << 1, r = mid;
		else id = id << 1 | 1, l = mid + 1;
	}
	st[id] += val;
	while (id > 1) {
		id >>= 1;
		st[id] = min(st[id << 1], st[id << 1 | 1]);
	}
}

int walk (int id, int l, int r, int u, int v) {
	if (l > v || r < u || st[id]) return - 1;
	if (l == r) return l;
	int mid = (l + r) >> 1;
	int ret = walk (id << 1 | 1, mid + 1, r, u, v);
	if (ret == - 1) ret = walk (id << 1, l, mid, u, v);
	return ret;
}

int find_root (int u) {
	while (cur[u] != cur[1]) {
		int root = walk (1, 1, n, pos[head[cur[u]]], pos[u]);
		if (root != - 1) return arr[root];
		u = par[head[cur[u]]];
	}
	int root = walk (1, 1, n, pos[1], pos[u]);
	return arr[root];
}	

void solve () {
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		edges[i] = make_pair(u, v);
		ke[u].push_back(v); ke[v].push_back(u);
	}
	dfs(1);
	hld(1);	
	for (int i = 1; i < n; i++) if (h[edges[i].first] > h[edges[i].second]) {
		swap(edges[i].first, edges[i].second);	
	}
	for (int i = 1; i <= n; i++) {
		ans[i] = 1;
	} 	
	while (m--) {
		int i; cin >> i;
		int u = edges[i].first, v = edges[i].second;

		state[i] ^= 1;
		if (state[i]) update(pos[v], 1);
		else update(pos[v], - 1);

		if (state[i] == 0) {
			ans[v] = last[v] = ans[find_root(u)];
		} else {
			ans[find_root(v)]+= ans[v] - last[v];
		}
	}
	while (q--) {
		int u; cin >> u;
		cout << ans[find_root(u)] << "\n";
	}
}

signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #define kieuoanh "JOI13_synchronization"

    if (fopen(kieuoanh".inp", "r")) {
        freopen(kieuoanh".inp", "r", stdin); freopen(kieuoanh".out", "w", stdout);
    }

    solve();

    return 0;
}

Compilation message (stderr)

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

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