제출 #1141358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141358		Saul0906	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 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 repr(a,b,c) for(int a=b-1; a>c-1; 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)>>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));
	vi qr;
	int x=0, y=N, z;
	while(__builtin_popcount(y)>1) y++;
	z=__lg(y);
	repr(i,z,0){
		qr.clear();
		int r=min(N-1,(x+(1<<i)));
		rep(j,0,r) qr.pb(nd[j].se);
		if(!query(qr)) x=r;
	}
	return nd[x].se;
}

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