oj.uz

Submission #578098

# Submission time Handle Problem Language Result Execution time Memory
578098 2022-06-16T04:47:39 Z amunduzbaev Spring cleaning (CEOI20_cleaning) C++17
34 / 100
 1000 ms 15500 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;

const int N = 1e5 + 5;
vector<int> edges[N];
int sub[N], nw[N], res;
int is[N];

void dfs(int u, int p = -1){
	sub[u] = nw[u] + is[u];
	for(auto x : edges[u]){
		if(x == p) continue;
		dfs(x, u);
		sub[u] += sub[x];
	}
	//~ cout<<u<<" "<<sub[u]<<"\n";
	if(!(sub[u] & 1)){
		//~ cout<<u<<"\n";
		res++;
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q; cin>>n>>q;
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	int cnt = 0;
	for(int i=1;i<=n;i++){
		is[i] = ((int)edges[i].size() == 1);
		cnt += is[i];
	}
	
	for(int i=0;i<q;i++){
		int d; cin>>d;
		vector<int> t, tmp;
		for(int x=0;x<d;x++){
			int p; cin>>p;
			nw[p]++;
			t.push_back(p);
			if(is[p]){
				is[p]--;
				cnt--;
			}
		}
		res = 0, dfs(1);
		if((cnt + d) & 1){
			cout<<-1<<"\n";
		} else {
			cout<<n - 1 + d + res - 1<<"\n";
		}
		for(auto p : t){
			nw[p]--;
			if((int)edges[p].size() == 1 && !is[p]){
				is[p] = 1;
				cnt++;
			}
		}
	}
}

Subtask #1
0.0 / 0.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3412 KB Output is correct
2 Correct 9 ms 3452 KB Output is correct
3 Correct 37 ms 7412 KB Output is correct
4 Correct 43 ms 7440 KB Output is correct
5 Correct 39 ms 9132 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3668 KB Output is correct
2 Correct 9 ms 3644 KB Output is correct
3 Correct 47 ms 14684 KB Output is correct
4 Correct 46 ms 15500 KB Output is correct
5 Correct 55 ms 14476 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 4300 KB Output is correct
2 Correct 145 ms 3540 KB Output is correct
3 Correct 225 ms 3524 KB Output is correct
4 Correct 237 ms 4052 KB Output is correct
5 Correct 209 ms 4308 KB Output is correct
6 Correct 254 ms 3964 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 5588 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 1092 ms 7040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

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