Submission #797786

#	Time	Username	Problem	Language	Result	Execution time	Memory
797786		MODDI	Easter Eggs (info1cup17_eastereggs)	C++14	66 / 100	39 ms	464 KiB

eastereggs

#//include "grader.cpp"
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
int n;
vi G[550], euler;
void dfs(int at, int p){
	euler.pb(at);
	for(auto next : G[at]){
		if(next == p)	continue;
		dfs(next, at);
		euler.pb(at);
	}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
    n = N;
    for(int i = 0; i < n; i++)	G[i].clear();
    for(auto t : bridges){
		G[t.first].pb(t.second);
		G[t.second].pb(t.first);
	}
	euler.clear();
	dfs(1, 0);
	int l = 0, r = (int)euler.size()-1, ans = -1;
	while(r-l>=1){
		int mid = (l + r) / 2;
		set<int> ask;
		for(int i = l; i <= mid; i++){
			ask.insert(euler[i]);
		}
		vi is;
		for(auto t : ask)	is.pb(t);
		int s = query(is);
		if(s == 1){
			ans = mid;
			r = mid;
		}
		else{
			l = mid+1;
		}
	}
	return euler[ans];
}

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