Submission #773768

#	Time	Username	Problem	Language	Result	Execution time	Memory
773768		khshg	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	24 ms	448 KiB

eastereggs

#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 (stderr)

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 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20