Submission #119651

#	Time	Username	Problem	Language	Result	Execution time	Memory
119651		Bruteforceman	Synchronization (JOI13_synchronization)	C++11	10 / 100	8063 ms	33248 KiB

synchronization

#include "bits/stdc++.h"
using namespace std;
int l[100010], r[100010];
int n; 
int par[100010];
vector <int> g[100010];

vector <int> t[500010];
int cur;
bool vis[100010];
int node[100010];
int sub[500010];


void dfs(int x, int p) {
	par[x] = p;
	for(auto e : g[x]) {
		int i = l[e] ^ r[e] ^ x;
		if(e - p) {
			dfs(i, e);
		}
	}
} 

int root(int u) {
	while(vis[par[u]]) {
		u ^= l[par[u]] ^ r[par[u]];
	}
	return u;
}

int cnt;

void subtree(int x) {
	if(sub[x] != -1) return ;
	sub[x] = 1;
	cnt += (x <= n);
	for(auto i : t[x]) {
		subtree(i);
	}
}

int main(int argc, char const *argv[])
{
	int m, qr;
	scanf("%d %d %d", &n, &m, &qr);
	
	for(int i = 1; i < n; i++) {
		scanf("%d %d", l + i, r + i);
		g[l[i]].push_back(i);
		g[r[i]].push_back(i);
	}
	dfs(1, 0);

	cur = n;
	for(int i = 1; i <= n; i++) {
		node[i] = i;
	}

	for(int i = 1; i <= m; i++) {
		int e;
		scanf("%d", &e);
		int u;
		if(par[l[e]] == e) {
			u = l[e];
		} else {
			u = r[e];
		}
		if(vis[e]) {
			node[u] = node[root(u)];
			vis[e] ^= 1;
		} else {
			vis[e] ^= 1;
			int r = root(u);
			int p = node[r];
			int q = node[u];
			node[r] = ++cur;
			t[cur].push_back(p);
			t[cur].push_back(q);
			// cout << cur << ' ' << p << endl;
			// cout << cur << ' ' << q << endl;
		}
	}
	
	for(int i = 1; i <= qr; i++) {
		int u;
		scanf("%d", &u);
		cnt = 0;
		memset(sub, -1, sizeof sub);
		subtree(node[root(u)]);
		printf("%d\n", cnt);
	}
	return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'int main(int, const char**)':
synchronization.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &qr);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", l + i, r + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &e);
   ~~~~~^~~~~~~~~~
synchronization.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &u);
   ~~~~~^~~~~~~~~~

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