Submission #80831

#	Time	Username	Problem	Language	Result	Execution time	Memory
80831		farukkastamonuda	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	22 ms	624 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#define fi first
#define se second
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define li 555
#define mp make_pair
#define pb push_back
using namespace std;
int cur,mark[li], now;
vector<int> v[li], send;
bool init;
void dfs(int node,int ata){
	if(now == cur/2) return ;
	now += (! mark[node]);
	send.pb(node);
	for(int i = 0;i < (int)v[node].size(); i++){
		int go = v[node][i];
		if(go != ata) dfs(go,node);
	}
}
int findEgg(int N, vector< pair<int, int> > bridges){
	for(int i=1;i<=N;i++) mark[i]=0;
	if(!init) {
		for(int i = 0; i < N - 1; i++){
			int x = bridges[i].fi;
			int y = bridges[i].se;
			v[x].pb(y);
			v[y].pb(x);
		}
		init=true;
	}
	cur = N;
	while(cur > 1){
		now = 0;
		dfs(1, 0);
		if(query(send) == 1){
			cur /= 2;
			for(int i = 1;i <= N ; i++){
				mark[i]++;
			}
			for(int i = 0;i < (int)send.size(); i++){
				mark[send[i]]--;
			}
		}
		else{
			cur = cur - cur / 2;
			for(int i = 0;i < (int)send.size(); i++){
				mark[send[i]]=1;
			}
		}
		send.clear();
	}
	for(int i = 1;i <= N; i++){
		if(mark[i] == 0) return i;
	}
}

Compilation message (stderr)

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

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