제출 #270462

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
270462		usuyus	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	24 ms	384 KiB

eastereggs

#include <bits/stdc++.h>
#define N 1001
using namespace std;

vector<int> tree[N], ord, temp;

int query(vector<int> islands);

void dfs(int node, int parent) {
	ord.push_back(node);
	for (int child : tree[node]) {
		if (child != parent) dfs(child, node);
	}
}

int findEgg(int n, vector<pair<int,int>> edges) {
	ord.clear();
	for (int i=1; i<=n; i++) tree[i].clear();

	for (int i=0; i<n-1; i++) {
		int a=edges[i].first, b=edges[i].second;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	dfs(1, 0);

	int l=1, r=n;
	while (l<r) {
		int m=(l+r)/2;
		temp.clear();
		temp.insert(temp.end(), ord.begin(), ord.begin()+m);
		
		int res = query(temp);
		if (res) r = m;
		else l=m+1;
	}

	return ord[l-1];
}

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