oj.uz

Submission #578246

# Submission time Handle Problem Language Result Execution time Memory
578246 2022-06-16T09:16:44 Z temporary_juggernaut Spring cleaning (CEOI20_cleaning) C++14
34 / 100
 1000 ms 25112 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
vector<int>g[200005];
ll dp[200005][2];
void dfs(int v,int p){
	for(int to:g[v])if(to^p)dfs(to,v);
	if(g[v].size()==1&&p){
		dp[v][0]=1e15;
		dp[v][1]=0;
		return;
	}
	dp[v][0]=dp[v][1]=0;
	vector<pair<ll,int>>vec;
	for(int to:g[v])if(to^p)vec.push_back(make_pair(dp[to][1]-dp[to][0],to));
	sort(vec.begin(),vec.end());
	{
		dp[v][1]+=dp[vec[0].sc][1]+1;
		for(int i=1;i<(int)vec.size();i++){
			if(i+1<(int)vec.size()){
				dp[v][1]+=min(dp[vec[i].sc][0]+dp[vec[i+1].sc][0]+4,dp[vec[i].sc][1]+dp[vec[i+1].sc][1]+2);
				i++;
			}else dp[v][1]+=dp[vec[i].sc][0]+2;
		}
	}
	{
		for(int i=0;i<(int)vec.size();i++){
			if(i+1<(int)vec.size()){
				dp[v][0]+=min(dp[vec[i].sc][0]+dp[vec[i+1].sc][0]+4,dp[vec[i].sc][1]+dp[vec[i+1].sc][1]+2);
				i++;
			}else dp[v][0]+=dp[vec[i].sc][0]+2;
		}
	}
}
int main(){
	int n,q;
	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);
	}
	dfs(1,0);
	if(n*q>50000000){
		if(__builtin_popcount(n+1)==1){
			while(q--){
				int m;
				scanf("%d",&m);
				int leaf=0;
				int cnt=0;
				while(m--){
					int x;
					scanf("%d",&x);
					if(g[x].size()==1)leaf++;
					else cnt++;
				}
				if(cnt&1)puts("-1");
				else printf("%lld\n",dp[1][0]+cnt+leaf);
			}
			return 0;
		}
	}
	while(q--){
		int m;
		scanf("%d",&m);
		vector<int>vec;
		int timer=n+1;
		while(m--){
			int x;
			scanf("%d",&x);
			vec.push_back(x);
			g[x].push_back(timer);
			g[timer].push_back(x);
			timer++;
		}
		dfs(1,0);
		ll ans=dp[1][g[1].size()==1];
		if(ans>=(1e15))ans=-1;
		printf("%lld\n",ans);
		timer=n+1;
		for(int &x:vec){
			g[x].pop_back();
			g[timer].clear();
			timer++;
		}
	}
}

Compilation message

cleaning.cpp: In function 'int main()':
cleaning.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
cleaning.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~
cleaning.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
cleaning.cpp:70:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |      scanf("%d",&x);
      |      ~~~~~^~~~~~~~~
cleaning.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d",&m);
      |   ~~~~~^~~~~~~~~
cleaning.cpp:87:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |    scanf("%d",&x);
      |    ~~~~~^~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9676 KB Output is correct
2 Correct 28 ms 9704 KB Output is correct
3 Correct 68 ms 14048 KB Output is correct
4 Correct 91 ms 16332 KB Output is correct
5 Correct 132 ms 18264 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 10440 KB Output is correct
2 Correct 46 ms 10380 KB Output is correct
3 Correct 133 ms 22124 KB Output is correct
4 Correct 133 ms 25112 KB Output is correct
5 Correct 113 ms 20472 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 7124 KB Output is correct
2 Correct 413 ms 6100 KB Output is correct
3 Correct 524 ms 5952 KB Output is correct
4 Correct 557 ms 6788 KB Output is correct
5 Correct 523 ms 7232 KB Output is correct
6 Correct 676 ms 6840 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 8060 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 1083 ms 9728 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 4948 KB Output is correct
2 Execution timed out 1070 ms 6220 KB Time limit exceeded
3 Halted 0 ms 0 KB -