Submission #1130719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130719		nikolashami	Easter Eggs (info1cup17_eastereggs)	C++20	87 / 100	11 ms	468 KiB

eastereggs

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

const int N=515;
vector<int>g[N];
int tour[N],point,n;

void dfs(int u,int p){
	tour[point++]=u;
	for(int v:g[u]){
		if(!(v^p))continue;
		dfs(v,u);
	}
}

vector<int>get(int x){
	vector<int>ret;
	for(int i=0;i<=x;++i)
		ret.push_back(tour[i]);
	return ret;
}

int findEgg(int N,vector<pair<int,int>>bridges){
	n=N;
	  for(int i=0;i<=N;++i)
	    g[i].clear();
    for(auto&[u,v]:bridges){
    	g[u].push_back(v);
    	g[v].push_back(u);
    }
    point=0;
    dfs(1,0);
    int l=0,r=n-1,ans=tour[n-1];
    while(l<=r){
    	int m=(l+r)/2;
    	if(query(get(m))){
    		r=m-1;
    		ans=tour[m];
    	}else
    		l=m+1;
    }
    return ans;
}

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