oj.uz

Submission #119386

# Submission time Handle Problem Language Result Execution time Memory
119386 2019-06-21T06:49:56 Z Bruteforceman Synchronization (JOI13_synchronization) C++11
0 / 100
 8000 ms 32860 KB 
#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;
}

void subtree(int x) {
	if(sub[x] != -1) return ;
	sub[x] = (x <= n);
	for(auto i : t[x]) {
		subtree(i);
		sub[x] += sub[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;
		}
	}
	memset(sub, -1, sizeof sub);
	for(int i = 1; i <= cur; i++) {
		subtree(i);
	}
	for(int i = 1; i <= qr; i++) {
		int u;
		scanf("%d", &u);
		printf("%d\n", sub[node[root(u)]]);
	}
	return 0;
}

Compilation message

synchronization.cpp: In function 'int main(int, const char**)':
synchronization.cpp:44: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:47: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:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &e);
   ~~~~~^~~~~~~~~~
synchronization.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &u);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 16512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8051 ms 25172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 16384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 32860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16560 KB Output is correct
2 Incorrect 16 ms 16356 KB Output isn't correct
3 Halted 0 ms 0 KB -