oj.uz

Submission #773768

# Submission time Handle Problem Language Result Execution time Memory
773768 2023-07-05T08:18:45 Z khshg Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 24 ms 448 KB 
#include "grader.h"
#include<bits/stdc++.h>
using namespace std;

int findEgg(int N, vector<pair<int, int>> bridges) {
	vector<vector<int>> adj(N);
	for(auto& u : bridges) {
		--u.first; --u.second;
		adj[u.first].push_back(u.second);
		adj[u.second].push_back(u.first);
	}
	vector<bool> good(N, 1);
	int sum = N;
	while(sum > 1) {
		vector<int> ask;
		vector<pair<int, int>> q;
		int goal = sum / 2;
		q.push_back({0, -1});
		while(true) {
			pair<int, int> s = q.back(); q.pop_back();
			ask.push_back(s.first + 1);
			goal -= good[s.first];
			if(goal == 0) break;
			for(int& u : adj[s.first]) {
				if(u != s.second) {
					q.push_back({u, s.first});
				}
			}
		}
		bool f = query(ask);
		vector<bool> ch(N);
		for(auto& u : ask) ch[u - 1] = 1;
		sum = 0;
		for(int i = 0; i < N; ++i) {
			if(good[i]) good[i] = (f ? ch[i] : !ch[i]);
			sum += good[i];
		}
	}
	for(int i = 0; i < N; ++i) if(good[i]) return i + 1;
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:6:27: warning: control reaches end of non-void function [-Wreturn-type]
    6 |  vector<vector<int>> adj(N);
      |                           ^

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 5 ms 448 KB Number of queries: 8
2 Correct 11 ms 352 KB Number of queries: 9
3 Correct 16 ms 336 KB Number of queries: 9
4 Correct 15 ms 356 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 344 KB Number of queries: 9
2 Correct 21 ms 336 KB Number of queries: 9
3 Correct 20 ms 356 KB Number of queries: 9
4 Correct 20 ms 336 KB Number of queries: 9