oj.uz

Submission #119694

# Submission time Handle Problem Language Result Execution time Memory
119694 2019-06-21T21:46:36 Z Bruteforceman Synchronization (JOI13_synchronization) C++11
100 / 100
 2210 ms 64976 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);
		}
	}
}
 
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];

int nxt[100010];
int head[100010];
int pos[100010];
int rev[100010];

set <int> s[100010];

void hld(int x, int p) {
	sub[x] = 1;
	nxt[x] = -1;
	for(auto e : g[x]) {
		int i = l[e] ^ r[e] ^ x;
		if(e != p && !del[i]) {
			hld(i, e);
			sub[x] += sub[i];
			if(nxt[x] == -1 || sub[nxt[x]] < sub[i]) {
				nxt[x] = i;
			}
		}
	}	
}

int root(int x) {
	while(true) {
		int h = head[x];
		if(s[h].empty() || *s[h].begin() > pos[x]) {
			x = h;
			x ^= l[par[x]] ^ r[par[x]];
		} else {
			return rev[*(--s[h].upper_bound(pos[x]))];
		}
	}
	return 0;
}
void invert(int e) {
	int u;
	if(par[l[e]] == e) u = l[e];
	else u = r[e];
	vis[e] ^= 1;
	if(vis[e]) {
		s[head[u]].erase(pos[u]);
	} else {
		s[head[u]].insert(pos[u]);
	}
}
// int invert(int e) {
// 	vis[e] ^= 1;
// }
// int root(int u) {
// 	while(vis[par[u]]) {
// 		u ^= l[par[u]] ^ r[par[u]];
// 	}
// 	return u;
// }
 
void solve(int x, vector <int> Q) {
	dfs(x, 0);
	x = centroid(x, 0, sub[x] / 2);
	del[x] = true;
 
	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();
	}
	hld(x, 0);
	nodes.push_back(x);
	int idx = 0;
	for(int i : nodes) {
		int p = l[par[i]] ^ r[par[i]] ^ i;
		if(i == x || nxt[p] != i) {
			for(int j = i; j != -1; j = nxt[j]) {
				head[j] = i;
				pos[j] = ++idx;
				rev[idx] = j;
			}
		}
	}
	for(auto i : nodes) {
		vis[par[i]] = 0;
		sz[i] = 1;
		s[i].clear();
	}
	for(auto i : nodes) {
		s[head[i]].insert(pos[i]);
	}
	nodes.pop_back();

	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]) {
			invert(e);
			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 {
			invert(e);
		}
	}
	sort(cont.begin(), cont.end());
	for(auto i : cont) {
		ans[x] += i.cnt;
	}
	for(auto i : nodes) {
		if(vis[par[i]]) {
			invert(par[i]);
		}
		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)];
			invert(e);
		} else {
			invert(e);
		}
	}
	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:159:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int h = 0; h < Q.size(); h++) {
                 ~~^~~~~~~~~~
synchronization.cpp:190:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int h = 0; h < Q.size(); h++) {
                 ~~^~~~~~~~~~
synchronization.cpp:213:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pt < cont.size() && cont[pt].pos < last[i]) {
         ~~~^~~~~~~~~~~~~
synchronization.cpp:220: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:240: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:243: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:250:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
synchronization.cpp:257: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 10 ms 9856 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 9 ms 9756 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 13 ms 9984 KB Output is correct
7 Correct 77 ms 12152 KB Output is correct
8 Correct 72 ms 12144 KB Output is correct
9 Correct 75 ms 12152 KB Output is correct
10 Correct 1299 ms 34212 KB Output is correct
11 Correct 1424 ms 34672 KB Output is correct
12 Correct 2152 ms 64904 KB Output is correct
13 Correct 232 ms 27236 KB Output is correct
14 Correct 956 ms 28940 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 34540 KB Output is correct
2 Correct 408 ms 36372 KB Output is correct
3 Correct 687 ms 43368 KB Output is correct
4 Correct 671 ms 43052 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9856 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 17 ms 10240 KB Output is correct
7 Correct 130 ms 14712 KB Output is correct
8 Correct 2115 ms 64856 KB Output is correct
9 Correct 2162 ms 64976 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2210 ms 64916 KB Output is correct
2 Correct 708 ms 42180 KB Output is correct
3 Correct 706 ms 44160 KB Output is correct
4 Correct 703 ms 44120 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9856 KB Output is correct
3 Correct 9 ms 9856 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 14 ms 9984 KB Output is correct
6 Correct 74 ms 12144 KB Output is correct
7 Correct 1443 ms 34528 KB Output is correct
8 Correct 2181 ms 64628 KB Output is correct
9 Correct 244 ms 27112 KB Output is correct
10 Correct 956 ms 29040 KB Output is correct
11 Correct 441 ms 34688 KB Output is correct
12 Correct 468 ms 36816 KB Output is correct
13 Correct 726 ms 44264 KB Output is correct