Submission #1164586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164586		daoquanglinh2007	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	504 KiB

eastereggs

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 512;

int N;
vector <int> adj[NM+5];
vector <int> arr;

void dfs(int u, int p){
	arr.push_back(u);
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u);
	}
}

int findEgg(int _N, vector <pii> bridges){
    N = _N;
    for (int i = 1; i <= N; i++) adj[i].clear();
    for (pii p : bridges){
    	adj[p.fi].push_back(p.se);
    	adj[p.se].push_back(p.fi);
	}
	arr.clear();
	dfs(1, -1);
	
	int l = 0, r = N-2, res = N-1;
	while (l <= r){
		int mid = (l+r)/2;
		vector <int> h = {};
		for (int j = 0; j <= mid; j++) h.push_back(arr[j]);
		
		if (query(h)){
			res = mid;
			r = mid-1;
		}
		else l = mid+1;
	}
	return arr[res];
}

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