Submission #116009

#	Time	Username	Problem	Language	Result	Execution time	Memory
116009		tuanasanh	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	15 ms	384 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> t;
vector<int> adj[600];
void dfs(int node,int par){
	t.push_back(node);
	for(auto u:adj[node]){
		if(u!=par) dfs(u,node);
	}
}
bool check(int m){
	vector<int> tmp;
	for(int i=0;i<=m;i++) tmp.push_back(t[i]);
	return query(tmp);
}
int findEgg (int n, vector < pair < int, int > > bridges)
{
    if(t.empty()){
    	for(auto p:bridges){
    		adj[p.first].push_back(p.second);
    		adj[p.second].push_back(p.first);
		}
		dfs(1,0);
	}
	int l=0,r=n-1;
	while(l<r){
		int m=(l+r)/2;
		if(check(m)) r=m;
		else l=m+1;
	}
	return t[l];
}

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