Submission #1146433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146433		Nurislam	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	9 ms	488 KiB

eastereggs

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

using namespace std;

int findEgg (int n, vector < pair < int, int > > bridges){
	
	vector<vector<int>> g(n + 5);
	for(auto [a, b] : bridges) {
		g[a].push_back(b);
		g[b].push_back(a);
	};
	
	vector<int> tin(n + 5, 0);
	int tim = 1;
	
	auto dfs = [&](auto dfs, int ps, int pr) -> void{
		tin[ps] = tim++;
		
		for(int to : g[ps])
			if(to != pr)
				dfs(dfs, to, ps);
				
	};
	dfs(dfs, 1, 1);
	
	int ans = 1;
	int l = 1, r = n;
	
	while(l < r){
		int m = (l+r)>>1;
		vector<int> lf;
		for(int i = 1; i <= n; i++)
			if(tin[i] <= m)
				lf.push_back(i);
		
		if(query(lf)){
			ans = m;
			r = m;
		}else{
			ans = m+1;
			l = m + 1;
		}
		
		
	};
	
	for(int i = 1; i <= n; i++){
		if(tin[i] == ans){
			ans = i;
			break;
		}
	}
	return ans;
	
}

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