Submission #116227

#	Time	Username	Problem	Language	Result	Execution time	Memory
116227		Just_Solve_The_Problem	Synchronization (JOI13_synchronization)	C++11	100 / 100	326 ms	21236 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

const int N = (int)2e5 + 7;

vector<int> gr[N];
vector<pair<int, int>> ed;

int n, m, q;
int tin[N], tout[N], pos[N];
int st[N];
int tiktak;
int tree[N * 4], ans[N], lst[N];

void dfs(int v, int pr) {
	tin[v] = ++tiktak;
	pos[tiktak] = v;
	for (int id : gr[v]) {
		int to = ed[id].first + ed[id].second - v;
		if (to == pr) continue;
		dfs(to, v);
	}
	tout[v] = ++tiktak;
}

void build(int v, int l, int r) {
	if (l == r) {
		tree[v] = tout[pos[l]];
		return ;
	}
	int mid = (l + r) >> 1;
	build(v + v, l, mid);
	build(v + v + 1, mid + 1, r);
	tree[v] = max(tree[v + v], tree[v + v + 1]);
}

void upd(int pos, int val, int v = 1, int tl = 1, int tr = n + n) {
	if (tl == tr) {
		tree[v] = val;
		return ;
	}
	int mid = (tl + tr) >> 1;
	if (pos <= mid) {
		upd(pos, val, v + v, tl, mid);
	} else {
		upd(pos, val, v + v + 1, mid + 1, tr);
	}
	tree[v] = max(tree[v + v], tree[v + v + 1]);
}

int find(int l, int r, int lim, int v = 1, int tl = 1, int tr = n + n) {
	if (tl > r || tr < l || tree[v] <= lim) return -1;
	if (tl == tr) return tl;
	int mid = (tl + tr) >> 1;
	int res = find(l, r, lim, v + v + 1, mid + 1, tr);
	if (res == -1) res = find(l, r, lim, v + v, tl, mid);
	return res;
}

int get(int l, int r, int v = 1, int tl = 1, int tr = n + n) {
	if (tl > r || tr < l) return -1;
	if (l <= tl && tr <= r) return tree[v];
	int mid = (tl + tr) >> 1;
	return max(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
}

int findroot(int u) {
	int res = find(1, tin[u], tin[u]);
	return (res == -1) ? 1 : pos[res];
}

main() {
	scanf("%d %d %d", &n, &m, &q);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		gr[u].push_back(ed.size());
		gr[v].push_back(ed.size());
		ed.push_back({u, v});
	}
	dfs(1, 1);
	for (int i = 1; i <= n; i++) {
		ans[i] = 1;
	}
	for (int i = 0; i < n - 1; i++) {
		if (tin[ed[i].first] > tin[ed[i].second]) 
			swap(ed[i].first, ed[i].second);
	}
	build(1, 1, n + n);
	for (int i = 1; i <= m; i++) {
		int id;
		scanf("%d", &id); id--;
		int u = findroot(ed[id].first);
		int v = ed[id].second;
		if (!st[id]) {
			ans[u] += ans[v] - lst[v];
			upd(tin[v], tin[v]);
		} else {
			ans[v] = lst[v] = ans[u];
			upd(tin[v], tout[v]);
		}
		st[id] ^= 1;
		//cout << find(1, tin[ed[id].first], tin[ed[id].first]) << ' ' << ed[id].first << ' ' << u << endl;
		//cout << "ZASDSDA " << get(2, 2) << endl;
	}
	for (int i = 1; i <= n; i++) {
		ans[i] = ans[findroot(i)];
	}
	for (int i = 1, x; i <= q; i++) {
		scanf("%d", &x);
		printf("%d\n", ans[x]);
	}
}

Compilation message (stderr)

synchronization.cpp:73:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &id); id--;
   ~~~~~^~~~~~~~~~~
synchronization.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

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