oj.uz

Submission #602753

# Submission time Handle Problem Language Result Execution time Memory
602753 2022-07-23T11:00:23 Z vanic Spring cleaning (CEOI20_cleaning) C++14
34 / 100
 1000 ms 18624 KB 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=2e5+5;

vector < int > ms[maxn];
vector < int > novi;

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){
		br++;
	}
	if(br&1){
		sol++;
	}
	else{
		sol+=2;
	}
	return br;
}

void rijesi(){
	sol=0;
	if(dfs(root, root)==-1){
		cout << -1 << '\n';
		return;
	}
	cout << sol << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	cin >> n >> q;
	int a, b;
	for(int i=0; i<n-1; i++){
		cin >> a >> 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;
		}
	}
	int m;
	for(int i=0; i<q; i++){
		cin >> m;
		for(int j=0; j<m; j++){
			cin >> a;
			a--;
			ms[a].push_back(j+n);
			ms[j+n].push_back(a);
			novi.push_back(a);
			novi.push_back(j+n);
		}
		rijesi();
		for(int j=0; j<m*2; j++){
			ms[novi[j]].pop_back();
		}
		novi.clear();
	}
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB Output is correct
2 Execution timed out 1090 ms 6488 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9060 KB Output is correct
2 Correct 29 ms 8988 KB Output is correct
3 Correct 27 ms 9524 KB Output is correct
4 Correct 48 ms 12100 KB Output is correct
5 Correct 74 ms 13348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9536 KB Output is correct
2 Correct 22 ms 9484 KB Output is correct
3 Correct 51 ms 15584 KB Output is correct
4 Correct 87 ms 18624 KB Output is correct
5 Correct 32 ms 14412 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 6864 KB Output is correct
2 Correct 135 ms 6208 KB Output is correct
3 Correct 197 ms 5868 KB Output is correct
4 Correct 237 ms 6312 KB Output is correct
5 Correct 214 ms 6444 KB Output is correct
6 Correct 298 ms 6704 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 8012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 9640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB Output is correct
2 Execution timed out 1090 ms 6488 KB Time limit exceeded
3 Halted 0 ms 0 KB -