Submission #292937

#	Time	Username	Problem	Language	Result	Execution time	Memory
292937		arnold518	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	306 ms	36152 KiB

cleaning

#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, Q, M;
vector<int> adj[MAXN+10];
int dp[MAXN+10], par[MAXN+10][30], dep[MAXN+10], leaf, cnt[MAXN+10], val, root;
int L[MAXN+10], R[MAXN+10], dfn;
pii dp2[MAXN+10];

void dfs(int now, int bef, int d)
{
	L[now]=++dfn;
	par[now][0]=bef;
	dep[now]=d;
	dp[now]=0;
	if(adj[now].size()==1)
	{
		dp[now]=1;
		R[now]=dfn;
		return;
	}
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, d+1);
		dp[now]+=dp[nxt];
		dp[now]%=2;
	}
	R[now]=dfn;
}

pii operator + (const pii &p, const pii &q) { return {p.first+q.first, p.second+q.second}; }
pii operator - (const pii &p, const pii &q) { return {p.first-q.first, p.second-q.second}; }

void dfs2(int now, int bef, pii val)
{
	if(now!=bef)
	{
		if(dp[now]==0) val.first++;
		else if(dp[now]==1) val.second++;
	}
	dp2[now]=val;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs2(nxt, now, val);
	}
}

int lca(int u, int v)
{
	if(dep[u]>dep[v]) swap(u, v);
	for(int i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) v=par[v][i];
	if(u==v) return u;
	for(int i=20; i>=0; i--) if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
	return par[u][0];
}

int dp3[MAXN+10];
vector<int> adj2[MAXN+10];
int ans=0;

void dfs3(int now, int bef)
{
	for(int nxt : adj2[now])
	{
		if(nxt==bef) continue;
		//printf("Edge %d %d\n", nxt, now);
		dfs3(nxt, now);
		dp3[now]+=dp3[nxt];
		dp3[now]%=2;
	}
	//printf("%d : %d / %d %d\n", now, dp3[now], dp2[now].first, dp2[now].second);
	if(now!=bef)
	{
		if(dp3[now])
		{
			pii t=dp2[now]-dp2[bef];
			ans-=t.first*2+t.second;
			ans+=t.first+t.second*2;
		}
	}
}

int main()
{
	scanf("%d%d", &N, &Q);
	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for(int i=1; i<=N; i++) if(adj[i].size()==1) leaf++;

	for(int i=1; i<=N; i++) if(adj[i].size()!=1) { root=i; break; }
	dfs(root, root, 1);
	dfs2(root, root, pii(0, 0));
	
	for(int i=1; i<=N; i++)
	{
		if(i==root) continue;
		if(dp[i]==0) val+=2;
		else val+=1;
	}
	for(int j=1; j<=20; j++) for(int i=1; i<=N; i++) par[i][j]=par[par[i][j-1]][j-1];

	while(Q--)
	{
		scanf("%d", &M);
		vector<int> V, V2;
		for(int i=1; i<=M; i++)
		{
			int t;
			scanf("%d", &t);
			V.push_back(t);
		}

		sort(V.begin(), V.end()); V2=V;
		V2.erase(unique(V2.begin(), V2.end()), V2.end());

		int lt=leaf;
		for(auto it : V2) if(adj[it].size()==1) lt--;
		lt+=M;

		if(lt%2) { printf("-1\n"); continue; }

		for(auto it : V) cnt[it]++;

		vector<int> VV=V2;
		sort(VV.begin(), VV.end(), [&](const int &p, const int &q){ return L[p]<L[q]; });

		int t=VV.size();
		for(int i=0; i+1<t; i++) VV.push_back(lca(VV[i], VV[i+1]));
		VV.push_back(root);

		sort(VV.begin(), VV.end(), [&](const int &p, const int &q){ return L[p]<L[q]; });
		VV.erase(unique(VV.begin(), VV.end()), VV.end());

		vector<int> S;
		for(int i=0; i<VV.size(); i++)
		{
			while(!S.empty() && !(L[S.back()]<=L[VV[i]] && R[VV[i]]<=R[S.back()])) S.pop_back();
			if(!S.empty()) adj2[S.back()].push_back(VV[i]);
			S.push_back(VV[i]);
		}

		for(auto it : V2)
		{
			if(adj[it].size()==1) dp3[it]=(cnt[it]-1)%2;
			else dp3[it]=cnt[it]%2;
		}

		ans=val+M;
		dfs3(root, root);

		printf("%d\n", ans);

		for(auto it : V) cnt[it]=0;
		for(auto it : VV) adj2[it].clear();
		for(auto it : VV) dp3[it]=0;
	}
}

Compilation message (stderr)

cleaning.cpp: In function 'int main()':
cleaning.cpp:149:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |   for(int i=0; i<VV.size(); i++)
      |                ~^~~~~~~~~~
cleaning.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
cleaning.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
cleaning.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |   scanf("%d", &M);
      |   ~~~~~^~~~~~~~~~
cleaning.cpp:123:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |    scanf("%d", &t);
      |    ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30