Submission #1195046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195046		ezdp	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	512 KiB

eastereggs

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;

template<class T> using matrix = vector<vector<T>>; 

void dfs(int u, int p, vector<int>& order, matrix<int>& G){
	order.push_back(u);
	for(auto v : G[u]){
		if(v == p) continue;
		dfs(v, u, order, G);
	}
}

int findEgg(int N, vector <pair<int, int>> bridges){
	matrix<int> G(N + 1);
	for(auto [u, v] : bridges){
		G[u].push_back(v);
		G[v].push_back(u);
	}
	vector<int> dfsorder;
	dfs(1, 1, dfsorder, G);
	int low = 0, high = N - 1;
	while(low < high){
		int mid = (low + high) / 2;
		vector<int> q = dfsorder;
		q.resize(mid + 1);
		if(query(q)){
			high = mid;
		}
		else{
			low = mid + 1;
		}
	}
	return dfsorder[low];
}

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