Submission #227779

#	Time	Username	Problem	Language	Result	Execution time	Memory
227779		arnold518	Synchronization (JOI13_synchronization)	C++14	0 / 100	8054 ms	48152 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int N, M, Q;
pii E[MAXN+10];
vector<int> A[MAXN+10];

vector<pii> adj[MAXN+10];
int sz[MAXN+10], del[MAXN+10];
int par[MAXN+10], edge[MAXN+10], head[MAXN+10];

void getsz(int now, int bef)
{
	sz[now]=1;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		par[nxt.first]=now;
		edge[nxt.first]=nxt.second;
		getsz(nxt.first, now);
		sz[now]+=sz[nxt.first];
	}
}

int getcen(int now, int bef, int S)
{
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		if(sz[nxt.first]>S/2) return getcen(nxt.first, now, S);
	}
	return now;
}

int idx[MAXN+10], invidx[MAXN+10], cnt;

struct UF
{
	int par[MAXN+10];
	int Find(int x) { return x==par[x] ? x : par[x]=Find(par[x]); }
	int Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		if(x==y) return x;
		par[x]=y;
		return y;
	}
}uf;

set<int> S[MAXN+10];
vector<int> V;

void hld(int now, int bef)
{
	//printf("!%d\n", now);
	V.push_back(now);
	idx[now]=++cnt;
	invidx[idx[now]]=now;
	int heavy=0;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		if(sz[heavy]<sz[nxt.first]) heavy=nxt.first;
	}

	if(heavy==0) return;
	head[heavy]=head[now];
	hld(heavy, now);

	for(auto nxt : adj[now])
	{	
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		if(nxt.first==heavy) continue;
		head[nxt.first]=nxt.first;
		hld(nxt.first, now);
	}
}

int col[MAXN+10], val[MAXN+10], ts[MAXN+10], te[MAXN+10];
int ans[MAXN+10];

void fs(int now)
{
	for(auto it : V)
	{
		uf.par[it]=it;
		col[it]=1;
		val[it]=it;
		S[it].clear();
		ts[it]=M+1;
	}

	for(auto it : V) S[head[it]].insert(idx[it]);

	vector<pii> VT;
	for(auto it : V) if(it!=now) for(auto jt : A[edge[it]]) VT.push_back({jt, it});
	sort(VT.begin(), VT.end());
	
	for(auto it : VT)
	{
		int v=it.second, t=it.first;
		if(col[v])
		{
			S[head[v]].erase(idx[v]);

			if(val[v])
			{
				int u=v;
				while(1)
				{
					auto pt=S[head[u]].upper_bound(idx[u]);
					if(pt==S[head[u]].begin()) u=par[head[u]];
					else { u=invidx[*(--pt)]; break; }
				}

				if(u==now)
				{
					if(val[v]) ts[val[v]]=t;
				}
				else
				{
					if(val[u]==0) val[u]=val[v];
					else val[u]=uf.Union(val[u], val[v]);
				}
				val[v]=0;
			}
			col[v]=0;
		}
		else	
		{
			S[head[v]].insert(idx[v]);
			col[v]=1;
		}
	}

	for(auto it : V) if(it!=now) ts[it]=ts[uf.Find(it)];
}

void fe(int now)
{
	for(auto it : V)
	{
		uf.par[it]=it;
		col[it]=1;
		val[it]=it;
		S[it].clear();
		te[it]=0;
	}

	for(auto it : V) S[head[it]].insert(idx[it]);

	vector<pii> VT;
	for(auto it : V) if(it!=now) for(auto jt : A[edge[it]]) VT.push_back({jt, it});
	sort(VT.begin(), VT.end(), greater<pii>());
	
	for(auto it : VT)
	{
		int v=it.second, t=it.first;
		if(col[v])
		{
			S[head[v]].erase(idx[v]);

			if(val[v])
			{
				int u=v;
				while(1)
				{
					auto pt=S[head[u]].upper_bound(idx[u]);
					if(pt==S[head[u]].begin()) u=par[head[u]];
					else { u=invidx[*(--pt)]; break; }
				}

				if(u==now)
				{
					if(val[v]) te[val[v]]=t;
				}
				else
				{
					if(val[u]==0) val[u]=val[v];
					else val[u]=uf.Union(val[u], val[v]);
				}
				val[v]=0;
			}
			col[v]=0;
		}
		else	
		{
			S[head[v]].insert(idx[v]);
			col[v]=1;
		}

		for(auto it : V) if(it!=now) te[it]=te[uf.Find(it)];
	}

	for(auto it : V) if(it!=now) te[it]=te[uf.Find(it)];
}

void dfs2(int now, int bef, vector<int> &VV)
{
	VV.push_back(now);
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		dfs2(nxt.first, now, VV);
	}
}

void decomp(int now)
{
	int i, j;
	getsz(now, now);
	now=getcen(now, now, sz[now]);
	getsz(now, now);

	V.clear();
	head[now]=now;
	hld(now, now);

	fs(now); fe(now);
	//for(auto it : V) printf("%d : %d %d\n", it, ts[it], te[it]);

	for(auto it : V) if(it!=now && ts[it]<=M) ans[now]++;
	for(auto it : V) if(it!=now && te[it]>0) ans[it]++;

	vector<int> VV;
	for(auto it : V) if(it!=now) VV.push_back(ts[it]);
	sort(VV.begin(), VV.end());
	for(auto it : V) if(it!=now) ans[it]+=lower_bound(VV.begin(), VV.end(), te[it])-VV.begin();

	for(auto nxt : adj[now])
	{
		if(del[nxt.first]) continue;
		vector<int> chd, VVV;
		dfs2(nxt.first, now, chd);
		for(auto it : chd) VVV.push_back(ts[it]);
		sort(VVV.begin(), VVV.end());
		for(auto it : chd) ans[it]-=lower_bound(VVV.begin(), VVV.end(), te[it])-VVV.begin();
	}

	//for(auto it : V) printf("ANS %d : %d\n", it, ans[it]);
	
	del[now]=true;
	for(auto nxt : adj[now])
	{
		if(del[nxt.first]) continue;
		decomp(nxt.first);
	}
}

int main()
{
	int i, j;

	scanf("%d%d%d", &N, &M, &Q);
	for(i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		E[i]={u, v};
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}
	for(i=1; i<=M; i++)
	{
		int t;
		scanf("%d", &t);
		A[t].push_back(i);
	}
	for(i=1; i<N; i++) if(A[i].size()%2) A[i].push_back(M+1);
	decomp(1);
	
	for(i=1; i<=N; i++) ans[i]++;
	while(Q--)
	{
		int t;
		scanf("%d", &t);
		printf("%d\n", ans[t]);
	}
}

Compilation message (stderr)

synchronization.cpp: In function 'void decomp(int)':
synchronization.cpp:221:6: warning: unused variable 'i' [-Wunused-variable]
  int i, j;
      ^
synchronization.cpp:221:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:263:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
synchronization.cpp:265:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:269:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~
synchronization.cpp:277:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
synchronization.cpp:287:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40