oj.uz

Submission #762175

# Submission time Handle Problem Language Result Execution time Memory
762175 2023-06-21T03:15:24 Z siewjh Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 15 ms 348 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Number of queries: 4
2 Correct 1 ms 208 KB Number of queries: 4
3 Correct 1 ms 208 KB Number of queries: 4
4 Correct 1 ms 208 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 336 KB Number of queries: 8
2 Correct 13 ms 348 KB Number of queries: 9
3 Correct 15 ms 340 KB Number of queries: 9
4 Correct 13 ms 336 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 336 KB Number of queries: 9
2 Correct 13 ms 348 KB Number of queries: 9
3 Correct 14 ms 344 KB Number of queries: 9
4 Correct 12 ms 344 KB Number of queries: 9