Submission #1125377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125377		Matthewwww	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	13 ms	508 KiB

eastereggs

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second

void dfs (int i, int j, vector<vector<int>> &adj, vector<int> &order){
	order.push_back(i);
	for (int k : adj[i])
		if (k != j)
			dfs(k, i, adj, order);
}

bool _query (int k, vector<int> &vt){
	vector<int> vt2;
	for (int i = 0; i < k; i++)
		vt2.push_back(vt[i]+1);
	return query(vt2);
}

int findEgg (int n, vector<pair<int, int>> edges){
	vector<vector<int>> adj(n);
	for (auto i : edges){
		adj[i.f-1].push_back(i.s-1);
		adj[i.s-1].push_back(i.f-1);
	}
	vector<int> ord;
	int ans = 0;
	dfs(0, -1, adj, ord);
	for (int i = n <= 16 ? 4 : 9; i--;)
		if (ans+(1<<i) <= n && !_query(ans+(1<<i), ord))
			ans += 1<<i;
	return ord[ans]+1;
}

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