Submission #243029

#	Time	Username	Problem	Language	Result	Execution time	Memory
243029		umk	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	31 ms	2920 KiB

eastereggs

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

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

const int N = 1e5+5;
int ck[N], nw[N], cnt, cur, num;
vector <int> adj[N], ans;

void dfs(int u, int p){
	if (cur == num) return ;
	if (ck[u]) cur++;
	ans.pb(u);
	for (int i=0; i<(int)adj[u].size(); i++){
		int v = adj[u][i];
		if (v == p) continue;
		dfs(v, u);
	}
}

int findEgg(int n, vector <pair <int, int> > e){
	for (int i=1; i<=n; i++) ck[i] = 1;
	cnt = n;
	for (int i=1; i<=n; i++) adj[i].clear();
	for (int i=1; i<n; i++){
		adj[e[i-1].fi].pb(e[i-1].se);
		adj[e[i-1].se].pb(e[i-1].fi);
	} 
	while (cnt != 1){
		num = (cnt+1)>>1; cur = 0;
		ans.clear();
		dfs(1, 1);
		if (query(ans)){
			for (int i=1; i<=n; i++) nw[i] = 0;
			for (int i=0; i<(int)ans.size(); i++) nw[ans[i]] = ck[ans[i]];
			for (int i=1; i<=n; i++) ck[i] = nw[i];
			cnt = num;
		}
		else{
			for (int i=0; i<(int)ans.size(); i++) ck[ans[i]] = 0;
			cnt -= num;
		}
	}
	for (int i=1; i<=n; i++) if (ck[i]) return i;
}

Compilation message (stderr)

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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