제출 #1147192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147192		henriess	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	0 ms	412 KiB

eastereggs

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

using namespace std;

vector<int> vis;

vector<int> ord;
vector<vector<int>> adjlist;
void dfs(int x){
    vis[x] = 1;
    for (auto nxt : adjlist[x])
        if (!vis[nxt])
            dfs(nxt);
    ord.push_back(x);
}
int findEgg (int N, vector < pair < int, int > > bridges)
{	vis.resize(N);
	
	adjlist.resize(N);
	for(int i = 0;i<N-1;i++){
		long long a,b;cin >> a >> b;
		a--;b--;
		adjlist[a].push_back(b);
		adjlist[b].push_back(a);
	}
	
	dfs(0);
	reverse(ord.begin(),ord.end());
	long long lb = 0;
	long long ub = N-1;
	long long mid = -1;
	long long ans = -1;
	while (lb <= ub){
		mid = (lb + ub) / 2;
		vector<int> temp(mid+1);
		for(int i = 0;i<=mid;i++){
			temp[i] = ord[i];
		}
		int r = query(temp);
		if (r == 0){
			lb = mid + 1;
		}
		else{
			ub = mid - 1;
		}
		
	}
	return ord[lb];
}

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