Submission #119694

#	Time	Username	Problem	Language	Result	Execution time	Memory
119694		Bruteforceman	Synchronization (JOI13_synchronization)	C++11	100 / 100	2210 ms	64976 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40