Submission #1283657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283657		WH8	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	7 ms	480 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

int findEgg (int N, vector < pair < int, int > > bridges)
{
	vector<vector<int>> al(N+1);
	//~ assert((int)bridges.size()==N-1);
	for(int i=0;i<N-1;i++){
		al[bridges[i].first].push_back(bridges[i].second);
		al[bridges[i].second].push_back(bridges[i].first);
	}
	vector<bool> ex(N+1, 1);
	vector<int> sz(N+1, 1);
	while(true){
		//~ cout<<endl;
		int sm=0, root=0;

		for(int i=1;i<=N;i++){
			if(ex[i]){
				//~ printf("%d is in\n", i);
				sm++;
				root=i;
			}
		}
		if(sm==1)return root;
		vector<int> in;
		auto dfs=[&](auto dfs, int x, int p)->void{
			sz[x]=1;
			for(auto it:al[x]){
				if(it==p or !ex[it])continue;
				dfs(dfs, it, x);
				sz[x]+=sz[it];
			}
		};
		dfs(dfs, root, 0);
		auto dfs2=[&](auto dfs2, int x, int p)->void{
			for(auto it:al[x]){
				if(it==p or !ex[it])continue;
				if(sz[it]>=sm/2){
					//~ printf("sz[%d] is %d, sm is %d\n", it, sz[it], sm);
					dfs2(dfs2, it, x);
					return;
				}
			}
			//~ printf("%d, dz %d sm is %d\n", x, sz[x],sm);
			in.push_back(x);
			for(auto it:al[x]){
				if(it==p or !ex[it])continue;
				dfs2(dfs2, it, x);
			}
		};

		dfs2(dfs2, root, 0);
		//~ for(int i=1;i<=N;i++){
			//~ cout<<sz[i]<<" ";
		//~ }
		//~ cout<<endl;
		//~ for(auto it: in)cout<<it<<" ";
		//~ cout<<endl;
		if(query(in)){
			ex.assign(N+1, 0);
			for(auto it:in)ex[it]=1;
		}
		else{
			for(auto it:in)ex[it]=0;
		}
	}

}

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20