oj.uz

Submission #674110

# Submission time Handle Problem Language Result Execution time Memory
674110 2022-12-23T05:56:05 Z QwertyPi Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 24 ms 464 KB 
#include <vector>
#include <iostream>

using namespace std;

bool in[513] = {0, 0, 0, 0, 0, 1};

#ifdef TEST
int query(vector<int> islands){
	cout << "Query: ";
	for(auto i : islands){
		cout << i << ' ';
	}
	bool y = false;
	for(auto i : islands){
		y |= in[i];
	}
	cout << (y ? "YES" : "NO") << endl;
	return y;
}
#else
int query(vector<int> islands);
#endif

vector<int> G[513];

int c = 0, tot = 512;
int u[513], elim[513];
void dfs(int t, int v, int par = -1){
	if(c == tot) return;
	if(u[v] == 0) c++, u[v] = t;
	for(auto i : G[v]){
		if(i == par || elim[i])
			continue;
		dfs(t, i, v);
	}
}

int findEgg(int N, vector<pair<int, int>> bridges){
	if(N == 1) return 1;
	for(int i = 1; i <= N; i++){
		G[i].clear();
	}
	fill(u, u + N + 1, 0);
	fill(elim, elim + N + 1, 0);
	c = tot = 0;
	for(int i = 0; i < N - 1; i++){
		G[bridges[i].first].push_back(bridges[i].second);
		G[bridges[i].second].push_back(bridges[i].first);
	}
	for(int a = N, i = (N + 1) / 2, t = 1;; t++){
		c = 0; tot = i; dfs(t, 1);
		vector<int> islands;
		for(int j = 1; j <= N; j++){
			if(u[j]) islands.push_back(j);
		}
		int r = query(islands);
		if(!r){
			if(a - i == 1){
				for(int j = 1; j <= N; j++){
					if(u[j] == 0 && !elim[j]) return j;
				}
			}
			a = a - i; i = (a + 1) / 2;
		}else{
			if(i == 1){
				for(int j = 1; j <= N; j++){
					if(u[j] == t) return j;
				}
			}
			a = i; i = (a + 1) / 2;
			for(int j = 1; j <= N; j++){
				if(u[j] == 0) elim[j] = true;
				if(u[j] == t) u[j] = 0;
			}
		}
	}
	return 1;
}

#ifdef TEST
int main(){
	cout << findEgg(6, {{1, 2}, {1, 3}, {2, 4}, {4, 5}, {4, 6}}) << endl;
}
#endif

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 6 ms 336 KB Number of queries: 8
2 Correct 16 ms 352 KB Number of queries: 9
3 Correct 24 ms 464 KB Number of queries: 9
4 Correct 16 ms 356 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 368 KB Number of queries: 9
2 Correct 14 ms 360 KB Number of queries: 9
3 Correct 20 ms 356 KB Number of queries: 9
4 Correct 17 ms 344 KB Number of queries: 9