제출 #1283964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283964		WH8	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	10 ms	536 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

int findEgg (int N, vector < pair < int, int > > bridges)
{
	vector<vector<int>> al(N+1);
	assert((int)bridges.size()==N-1);
	for(int i=0;i<N-1;i++){
		al[bridges[i].first].push_back(bridges[i].second);
		al[bridges[i].second].push_back(bridges[i].first);
	}
	vector<int> ord;
	
	auto dfs=[&](auto dfs, int x, int p)->void{
		ord.push_back(x);
		for(auto it:al[x]){
			if(it==p)continue;
			dfs(dfs, it, x);
		}
	};
	dfs(dfs, 1, 0);
	int l=-1, r=N-1, m;
	while(l < r-1){
		m=(l+r)/2;
		vector<int> qry(ord.begin(), ord.begin()+m+1);
		if(query(qry)){
			r=m;
		}
		else {
			l=m;
		}
	}
	return ord[r];
}

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