oj.uz

Submission #578264

# Submission time Handle Problem Language Result Execution time Memory
578264 2022-06-16T09:42:11 Z temporary_juggernaut Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 160 ms 26148 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 48 ms 7912 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6868 KB Output is correct
2 Correct 33 ms 6808 KB Output is correct
3 Correct 52 ms 17416 KB Output is correct
4 Correct 71 ms 14964 KB Output is correct
5 Correct 94 ms 18452 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7492 KB Output is correct
2 Correct 41 ms 7440 KB Output is correct
3 Correct 66 ms 24836 KB Output is correct
4 Correct 106 ms 25964 KB Output is correct
5 Correct 54 ms 22780 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8516 KB Output is correct
2 Correct 24 ms 7572 KB Output is correct
3 Correct 17 ms 7424 KB Output is correct
4 Correct 15 ms 8020 KB Output is correct
5 Correct 16 ms 8156 KB Output is correct
6 Correct 34 ms 8292 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 13196 KB Output is correct
2 Correct 74 ms 13168 KB Output is correct
3 Correct 53 ms 9292 KB Output is correct
4 Correct 95 ms 13264 KB Output is correct
5 Correct 101 ms 13388 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 17756 KB Output is correct
2 Correct 147 ms 20604 KB Output is correct
3 Correct 151 ms 20636 KB Output is correct
4 Correct 123 ms 20112 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 48 ms 7912 KB Output is correct
3 Correct 42 ms 6868 KB Output is correct
4 Correct 33 ms 6808 KB Output is correct
5 Correct 52 ms 17416 KB Output is correct
6 Correct 71 ms 14964 KB Output is correct
7 Correct 94 ms 18452 KB Output is correct
8 Correct 41 ms 7492 KB Output is correct
9 Correct 41 ms 7440 KB Output is correct
10 Correct 66 ms 24836 KB Output is correct
11 Correct 106 ms 25964 KB Output is correct
12 Correct 54 ms 22780 KB Output is correct
13 Correct 50 ms 8516 KB Output is correct
14 Correct 24 ms 7572 KB Output is correct
15 Correct 17 ms 7424 KB Output is correct
16 Correct 15 ms 8020 KB Output is correct
17 Correct 16 ms 8156 KB Output is correct
18 Correct 34 ms 8292 KB Output is correct
19 Correct 65 ms 13196 KB Output is correct
20 Correct 74 ms 13168 KB Output is correct
21 Correct 53 ms 9292 KB Output is correct
22 Correct 95 ms 13264 KB Output is correct
23 Correct 101 ms 13388 KB Output is correct
24 Correct 105 ms 17756 KB Output is correct
25 Correct 147 ms 20604 KB Output is correct
26 Correct 151 ms 20636 KB Output is correct
27 Correct 123 ms 20112 KB Output is correct
28 Correct 80 ms 12760 KB Output is correct
29 Correct 135 ms 21260 KB Output is correct
30 Correct 75 ms 18592 KB Output is correct
31 Correct 134 ms 26148 KB Output is correct
32 Correct 81 ms 13400 KB Output is correct
33 Correct 121 ms 18440 KB Output is correct
34 Correct 160 ms 21500 KB Output is correct
35 Correct 159 ms 21560 KB Output is correct