Submission #762175

#	Time	Username	Problem	Language	Result	Execution time	Memory
762175		siewjh	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	15 ms	348 KiB

eastereggs

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

using namespace std;
const int MAXN = 520;
vector<int> adj[MAXN];
int state[MAXN]; // 0 still possible, 1 top out, 2 bottom out
vector<int> test;
int target;

void dfs(int x, int par){
	if (state[x] == 2) return;
	test.push_back(x);
	if (state[x] == 0) target--;
	for (int nxt : adj[x]){
		if (target == 0) break;
		if (nxt == par) continue;
		dfs(nxt, x);
	}
}

int findEgg (int N, vector<pair<int, int>> edges){
	for (int i = 1; i <= N; i++){
		adj[i].clear();
		state[i] = 0;
	}
	for(auto e : edges){
		int a, b; tie(a, b) = e;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	int poss = N;
	while (poss > 1){
		target = poss / 2;
		test.clear();
		dfs(1, -1);
		vector<bool> tested(N + 1, 0);
		for (int x : test) tested[x] = 1;
		if (query(test)){
			for (int i = 1; i <= N; i++)
				if (state[i] == 0 && !tested[i]){
					state[i] = 2;
					poss--;
				}
		}
		else{
			for (int i = 1; i <= N; i++)
				if (state[i] == 0 && tested[i]){
					state[i] = 1;
					poss--;
				}
		}
	}
	for (int i = 1; i <= N; i++)
		if (state[i] == 0)
			return i;
	return -1;
}

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