Submission #578264

#	Time	Username	Problem	Language	Result	Execution time	Memory
578264		juggernaut	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	160 ms	26148 KiB

cleaning

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int n,q;
vector<int>g[100001];
int leaves[100001],tot_leaves,bad;
bool is_leaf[100001];
int tin[100001],tout[100001],timer,up[100001][18];
vector<int>g2[100001];
int ans,bit[100001];
int a[100001],l_delta[100001];
void update(int pos,int val){for(;pos<=n;pos+=pos&-pos)bit[pos]+=val;}
int query(int l,int r,int res=0){res=0;for(;r;r-=r&-r)res+=bit[r];for(l--;l;l-=l&-l)res-=bit[l];return res;}
void lca_dfs(int node,int p=0){
	tin[node]=++timer;
	for(int i=1;i<18;i++)up[node][i]=up[up[node][i-1]][i-1];
	if(g[node].size()==1){
		leaves[node]=1;
		tot_leaves++;
		is_leaf[node]=true;
	}
	for(int i:g[node])if(i!=p){
		up[i][0]=node;
		lca_dfs(i,node);
		leaves[node]+=leaves[i];
	}
	tout[node]=timer;
	if(leaves[node]&1)update(tin[node],1),update(tout[node]+1,-1);
	else{
		update(tin[node],-1),update(tout[node]+1,1);
		bad++;
	}
}
bool upper(int u, int v){return tin[u]<=tin[v]&&tout[u]>=tout[v];}
int lca(int u, int v){
	if(upper(u,v))return u;
	for(int i=17;~i;i--)if(up[u][i]&&!upper(up[u][i],v))u=up[u][i];
	return up[u][0];
}
void g2_dfs(int node,int p=0){
	for(int i:g2[node])if(i!=p){
		g2_dfs(i,node);
		l_delta[node]+=l_delta[i];
	}
	ans+=(l_delta[node]&1)*query(tin[p]+1,tin[node]);
}
bool cmp(int u,int v){return tin[u]<tin[v];}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++)if(g[i].size()>1){
		lca_dfs(i);
		break;
	}
	while(q--){
		int d;
		scanf("%d",&d);
		vector<int>nodes;
		for(int i=0;i<d;i++){
			scanf("%d",&a[i]);
			if(is_leaf[a[i]])is_leaf[a[i]]=false;
			else{
				leaves[a[i]]++;
				tot_leaves++;
				l_delta[a[i]]++;
				nodes.push_back(a[i]);
			}
		}
		sort(nodes.begin(),nodes.end(),cmp);
		int m=nodes.size();
		for(int i=1;i<m;i++)nodes.push_back(lca(nodes[i-1],nodes[i]));
		sort(nodes.begin(),nodes.end(),cmp);
		nodes.erase(unique(nodes.begin(),nodes.end()),nodes.end());
		vector<int>stck;
		for(int i:nodes){
			while(stck.size()>1&&!upper(stck.back(),i)){
				g2[stck[stck.size()-2]].push_back(stck.back());
				stck.pop_back();
			}
			stck.push_back(i);
		}
		while(stck.size()>1){
			g2[stck[stck.size()-2]].push_back(stck.back());
			stck.pop_back();
		}
		if(tot_leaves&1)puts("-1");
		else{
			ans=n+d+bad-2;
			if(stck.size())g2_dfs(stck[0]);
			printf("%d\n",ans);
		}
		for(int i=0;i<d;i++){
			if(leaves[a[i]]==1)is_leaf[a[i]]=true;
			else{
				leaves[a[i]]--;
				tot_leaves--;
			}
		}
		for(int i:nodes){
			g2[i].clear();
			l_delta[i]=0;
		}
	}
}

Compilation message (stderr)

cleaning.cpp: In function 'int main()':
cleaning.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
cleaning.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~
cleaning.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d",&d);
      |   ~~~~~^~~~~~~~~
cleaning.cpp:81:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |    scanf("%d",&a[i]);
      |    ~~~~~^~~~~~~~~~~~

• 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