제출 #1130721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130721		nikolashami	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 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-2,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: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20