제출 #1195032

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195032		ezdp	Easter Eggs (info1cup17_eastereggs)	C++20	87 / 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, ans = -1;
	while(low <= high){
		int mid = (low + high) / 2;
		vector<int> q = dfsorder;
		q.resize(mid + 1);
		if(query(q)){
			ans = q.back();
			high = mid - 1;
		}
		else{
			low = mid + 1;
		}
	}
	return ans;
}

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