Submission #119692

#	Time	Username	Problem	Language	Result	Execution time	Memory
119692		Bruteforceman	Synchronization (JOI13_synchronization)	C++11	0 / 100	8061 ms	34652 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);
		}
	}
}

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;

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

synchronization.cpp: In function 'void solve(int, std::vector<int>&)':
synchronization.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int h = 0; h < Q.size(); h++) {
                 ~~^~~~~~~~~~
synchronization.cpp:122:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int h = 0; h < Q.size(); h++) {
                 ~~^~~~~~~~~~
synchronization.cpp:145:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pt < cont.size() && cont[pt].pos < last[i]) {
         ~~~^~~~~~~~~~~~~
synchronization.cpp:152: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:172: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:175: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:182:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
synchronization.cpp:189: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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40