제출 #1146767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146767		crispxx	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	484 KiB

eastereggs

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

// #include "grader.cpp"

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define nl '\n'

int findEgg(int n, vector <pair<int, int>> edges) {
	vector<vector<int>> adj(n);
	
	for(auto &[u, v] : edges) {
		u--, v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	
	queue<int> q;
	
	q.emplace(0);
	
	vector<int> used(n);
	
	used[0] = 1;
	
	vector<int> nod;
	
	while(!q.empty()) {
		int v = q.front();
		q.pop();
		
		nod.pb(v + 1);
		
		for(auto to : adj[v]) {
			if(!used[to]) {
				used[to] = 1;
				q.emplace(to);
			}
		}
	}
	
	
	int l = 0, r = (int)nod.size() - 1;
	
	while(l < r) {
		int mid = (l + r) >> 1;
		
		vector<int> T;
		for(int i = 0; i <= mid; i++) T.pb(nod[i]);
		
		if(query(T)) r = mid;
		else l = mid + 1;
	}
	
	return nod[l];
	
}

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