제출 #1160586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160586		thelegendary08	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	8 ms	508 KiB

eastereggs

#include <bits/stdc++.h>
#define pb push_back
#define f0r(i,n) for(int i= 0; i<n; i++)
#define vi vector<int>
#include "grader.h"

using namespace std;
vector<int>et;
const int mxn = 517;
vector<vector<int>> adj(mxn);
void dfs(int node, int from){
	et.pb(node);
	for(auto u : adj[node]){
		if(u != from){
			dfs(u, node);
		}
	}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
	et.clear();
	f0r(i, N+1){
		adj[i].clear();
	}
	if(N == 1)return 1;
	else{
		f0r(i, N-1){
			int a = bridges[i].first;
			int b = bridges[i].second;
			adj[a].pb(b);
			adj[b].pb(a);
		}
		dfs(1, 0);
		int lo = 1; 
		int hi = et.size();
		while(lo < hi){
			int mid = (lo + hi) / 2;
			vi quer;
			f0r(i,mid)quer.pb(et[i]);
			if(query(quer)){
				hi = mid;
			}
			else{
				lo = mid + 1;
			}
		}
		return et[lo-1];
	}
	
}

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