제출 #1141356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141356		Saul0906	Easter Eggs (info1cup17_eastereggs)	C++20	87 / 100	8 ms	492 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#define pii pair<int, int>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a:b)
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define mid ((l+r)>>1)
#define pb push_back

using namespace std;

using vi = vector<int>;

const int N=555;
vi adj[N];
int lvl[N];

void dfs(int u, int p){
	lvl[u]=lvl[p]+1;
	repa(v,adj[u]) if(v!=p) dfs(v,u);
}

int findEgg (int N, vector < pair < int, int > > bridges){
	rep(i,1,N+1) adj[i].clear();
	repa(e,bridges){
		adj[e.fi].pb(e.se);
		adj[e.se].pb(e.fi);
	}
	dfs(1,0);
	vector<pii> nd;
	rep(i,1,N+1) nd.pb({lvl[i],i});
	sort(all(nd));
	int l=0, r=N-1;
	vi qr;
	while(l<=r){
		qr.clear();
		rep(i,0,mid+1) qr.pb(nd[i].se);
		if(query(qr)) r=mid-1;
		else l=mid+1;
	}
	return nd[l].se;
}

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