oj.uz

Submission #602808

# Submission time Handle Problem Language Result Execution time Memory
602808 2022-07-23T11:28:57 Z vanic Spring cleaning (CEOI20_cleaning) C++14
26 / 100
 77 ms 14300 KB 
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=2e5+5;

vector < int > ms[maxn];
int novi[maxn];
bool koji[maxn];
int val[maxn];
int p[maxn];
int list;

int sol;
int root;

int dfs(int x, int prosl){
	int br=0;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			br+=dfs(ms[x][i], x);
		}
	}
	if(x==prosl){
		if(br&1){
			return 1;
		}
		return 0;
	}
	if(!br){
		list++;
		br++;
	}
	if(br&1){
		koji[x]=0;
		sol++;
	}
	else{
		koji[x]=1;
		sol+=2;
	}
	return br;
}

void rijesi(){
	sol=0;
	if(dfs(root, root)){
		printf("-1\n");
		return;
	}
	printf("%d\n", sol);
}

void scan(int &a){
	a=0;
	char c=getchar_unlocked();
	while(c>='0' && c<='9'){
		a*=10;
		a+=c-'0';
		c=getchar_unlocked();
	}
}

void odredi(int x, int prosl, int v){
	if(x!=prosl){
		if(koji[x]){
			v--;
		}
		else{
			v++;
		}
	}
	val[x]=v;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			odredi(ms[x][i], x, v);
		}
	}
}

int main(){
	int n, q;
	scan(n);
	scan(q);
	int a, b;
	for(int i=0; i<n-1; i++){
		scan(a);
		scan(b);
		a--;
		b--;
		ms[a].push_back(b);
		ms[b].push_back(a);
	}
	for(int i=0; i<n; i++){
		if(ms[i].size()>1){
			root=i;
			break;
		}
	}
	dfs(root, root);
	odredi(root, root, 0);
	int m;
	int sole;
	int liste;
	for(int i=0; i<q; i++){
		sole=sol;
		liste=list;
		scan(m);
		for(int j=0; j<m; j++){
			scan(a);
			a--;
			novi[j]=a;
			sole++;
			if(ms[a].size()==1){
				if(p[a]){
					if(p[a]&1){
						sole+=val[a];
					}
					else{
						sole-=val[a];
					}
					liste++;
				}
			}
			else{
				liste++;
				if(p[a]&1){
					sole-=val[a];
				}
				else{
					sole+=val[a];
				}
			}
			p[a]++;
		}
		if(liste&1){
			printf("-1\n");
		}
		else{
			printf("%d\n", sole);
		}
		for(int j=0; j<m; j++){
			p[novi[j]]=0;
		}
	}
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 14 ms 6280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5460 KB Output is correct
2 Correct 5 ms 5484 KB Output is correct
3 Correct 24 ms 9492 KB Output is correct
4 Correct 19 ms 8580 KB Output is correct
5 Correct 23 ms 9776 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 6028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 6628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8540 KB Output is correct
2 Incorrect 27 ms 8936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 10376 KB Output is correct
2 Correct 62 ms 14300 KB Output is correct
3 Correct 77 ms 14292 KB Output is correct
4 Correct 49 ms 13724 KB Output is correct

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 14 ms 6280 KB Output isn't correct
3 Halted 0 ms 0 KB -