Submission #589617

#	Time	Username	Problem	Language	Result	Execution time	Memory
589617		shezitt	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	20 ms	764 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int N = 520;
int n;
vector<int> g[N];
vector<int> a;
bool vis[N];

void dfs(int i){
	a.push_back(i);
	vis[i] = 1;
	for(auto x : g[i]){
		if(!vis[x]){
			dfs(x);
		}
	}
}

int findEgg (int nn, vector < pair < int, int > > bridges)
{
	memset(vis, 0, sizeof vis);
	n = nn;
	for(auto b : bridges){
		g[b.first].push_back(b.second);
		g[b.second].push_back(b.first);
	}
	dfs(1);
	int l = 0, r = n-2, ans = a[n-1];
	while(l <= r){
		int mid = (l+r)/2;
		vector<int> aux;
		for(int j=0; j<=mid; ++j){
			aux.push_back(a[j]);
		}
		if(query(aux)){
			ans = a[mid];
			r = mid-1;
		} else {
			l = mid+1;
		}
	}
	return ans;
}

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