oj.uz

Submission #119691

# Submission time Handle Problem Language Result Execution time Memory
119691 2019-06-21T21:12:40 Z Bruteforceman Synchronization (JOI13_synchronization) C++11
20 / 100
 8000 ms 38232 KB 
#include "bits/stdc++.h"
using namespace std;
int l[100010], r[100010];
int n; 
int par[100010];
vector <int> g[100010];

int sub[100010];
bool del[100010];
int rt[100010];
bool vis[100010];
int sz[100010];
int last[100010];
vector <int> aux[100010];

void dfs(int x, int p) {
	sub[x] = 1;
	for(auto e : g[x]) {
		int i = l[e] ^ r[e] ^ x;
		if(e != p && !del[i]) {
			dfs(i, e);
			sub[x] += sub[i];
		}
	}
} 
int centroid(int x, int p, int range) {
	for(auto e : g[x]) {
		int i = l[e] ^ r[e] ^ x;
		if(e != p && sub[i] > range && !del[i]) {
			return centroid(i, e, range);
		}
	}
	return x;
}

vector <int> nodes;
void prec(int x, int p, int src) {
	par[x] = p;
	rt[x] = src;
	nodes.push_back(x);
	for(auto e : g[x]) {
		int i = l[e] ^ r[e] ^ x;
		if(e != p && !del[i]) {
			prec(i, e, src);
		}
	}
}

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

struct data {
	int r, cnt, pos;
	data (int r, int cnt, int pos) : r(r), cnt(cnt), pos(pos) {}
	data () {}
	bool operator < (data f) const {
		return pos < f.pos;
	}
};
bool cmp(int i, int j) {
	return last[i] < last[j];
}

int ans[100010];
int sum[100010];

void solve(int x, vector <int> Q) {
	dfs(x, 0);
	x = centroid(x, 0, sub[x] / 2);
	del[x] = true;

	// cout << x << endl;

	nodes.clear();
	par[x] = 0;
	for(auto e : g[x]) {
		int i = l[e] ^ r[e] ^ x;
		if(del[i]) continue;
		prec(i, e, i);
		sum[i] = 0;
		aux[i].clear();
	}

	for(auto i : nodes) {
		vis[par[i]] = 0;
		sz[i] = 1;
	}
	vector <data> cont;
	sum[x] = 0;
	cont.emplace_back(x, 1, -1);
	for(int h = 0; h < Q.size(); h++) {
		int e = Q[h];
		int u;
		if(par[l[e]] == e) u = l[e];
		else u = r[e];

		if(!vis[e]) {
			vis[e] ^= 1;
			if(root(u) == x) {
				if (sz[u] > 0) {
					cont.emplace_back(rt[u], sz[u], h);
				}
				sz[u] = 0;
			} else {
				sz[root(u)] += sz[u];
				sz[u] = 0;
			}
		} else {
			vis[e] ^= 1;
		}
	}
	sort(cont.begin(), cont.end());
	for(auto i : cont) {
		ans[x] += i.cnt;
	}
	for(auto i : nodes) {
		vis[par[i]] = 0;
		last[i] = INT_MIN;
	}
	for(int h = 0; h < Q.size(); h++) {
		int e = Q[h];
		int u;
		if(par[l[e]] == e) u = l[e];
		else u = r[e];
		last[x] = h;

		if(vis[e]) {
			last[u] = last[root(u)];
			vis[e] ^= 1;
		} else {
			vis[e] ^= 1;
		}
	}
	last[x] = Q.size();
	for(auto i : nodes) {
		last[i] = last[root(i)];
	}
	sort(nodes.begin(), nodes.end(), cmp);

	int pt = 0;
	int tot = 0;
	for(int i : nodes) {
		while(pt < cont.size() && cont[pt].pos < last[i]) {
			sum[cont[pt].r] += cont[pt].cnt; 
			tot += cont[pt].cnt;
			++pt;
		}
		ans[i] += tot - sum[rt[i]];
	}
	for(int h = 0; h < Q.size(); h++) {
		int e = Q[h];
		int u;
		if(par[l[e]] == e) u = l[e];
		else u = r[e];
		if(rt[u] != u) {
			aux[rt[u]].push_back(e);
		}
	}

	for(auto e : g[x]) {
		int i = l[e] ^ r[e] ^ x;
		if(del[i]) continue;
		solve(i, aux[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);
	}
	vector <int> Q;
	for(int i = 1; i <= m; i++) {
		int x;
		scanf("%d", &x);
		Q.push_back(x);
	}
	solve(1, Q);

	for(int i = 1; i <= qr; i++) {
		int u;
		scanf("%d", &u);
		printf("%d\n", ans[u]);
	}
	return 0;
}

Compilation message

synchronization.cpp: In function 'void solve(int, std::vector<int>)':
synchronization.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int h = 0; h < Q.size(); h++) {
                 ~~^~~~~~~~~~
synchronization.cpp:124:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int h = 0; h < Q.size(); h++) {
                 ~~^~~~~~~~~~
synchronization.cpp:147:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pt < cont.size() && cont[pt].pos < last[i]) {
         ~~~^~~~~~~~~~~~~
synchronization.cpp:154:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int h = 0; h < Q.size(); h++) {
                 ~~^~~~~~~~~~
synchronization.cpp: In function 'int main(int, const char**)':
synchronization.cpp:174: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:177: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:184:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
synchronization.cpp:191:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &u);
   ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 5 ms 4992 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 7 ms 5248 KB Output is correct
7 Correct 29 ms 6784 KB Output is correct
8 Correct 29 ms 6776 KB Output is correct
9 Correct 31 ms 6648 KB Output is correct
10 Correct 437 ms 21648 KB Output is correct
11 Correct 538 ms 21940 KB Output is correct
12 Correct 381 ms 36208 KB Output is correct
13 Correct 86 ms 16964 KB Output is correct
14 Correct 405 ms 18380 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 5 ms 5120 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 38 ms 8184 KB Output is correct
8 Correct 409 ms 36336 KB Output is correct
9 Correct 410 ms 38144 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 36412 KB Output is correct
2 Execution timed out 8035 ms 22168 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 32 ms 6752 KB Output is correct
7 Correct 495 ms 22192 KB Output is correct
8 Correct 398 ms 38232 KB Output is correct
9 Correct 106 ms 18280 KB Output is correct
10 Correct 427 ms 20076 KB Output is correct
11 Execution timed out 8010 ms 19756 KB Time limit exceeded
12 Halted 0 ms 0 KB -