Submission #969512

#	Time	Username	Problem	Language	Result	Execution time	Memory
969512		tamir1	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	12 ms	1252 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#define ff first
#define ss second
using namespace std;
vector<int> v[1009],u,m;
void dfs(int x,int p){
	u.push_back(x);
	for(int i:v[x]){
		if(i!=p) dfs(i,x);
	}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
	u={0};
    int i;
	for(i=1;i<=N;i++) v[i].clear();
    for(i=0;i<N-1;i++){
    	int x=bridges[i].ff;
    	int y=bridges[i].ss;
    	v[x].push_back(y);
    	v[y].push_back(x);
	}
	dfs(1,-1);
    int mid,l=1,r=N;
    while(r>l){
    	mid=(r+l)/2;
    	m.clear();
    	for(i=1;i<=mid;i++) m.push_back(u[i]);
    	if(query(m)) r=mid;
    	else l=mid+1;
	}
	return u[r];
}

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