Submission #1139593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139593		KasymK	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	7 ms	508 KiB

eastereggs

#include "bits/stdc++.h"
#include "grader.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 550;
vector<int> adj[N], A;
// int select=4;

void dfs(int x, int pr=-1){
	A.pb(x);
	tr(it, adj[x])
	if(*it!=pr)
		dfs(*it, x);
}

// int query(vector<int> v){
// 	bool fnd=0;
// 	tr(it, v)
// 	if(*it==select){
// 		fnd=1;
// 		break;
// 	}
// 	return fnd;
// }

int findEgg(int n, vector<pii> v){
	A.clear();
	for(int i = 0; i <= n; ++i)
		adj[i].clear();
	tr(it, v)
	adj[it->ff].pb(it->ss), adj[it->ss].pb(it->ff);	
	dfs(1);
	int l=0, r=(int)A.size()-1;
	while(l<r){
		int m=(l+r)>>1;
		if(query({A.begin(), A.begin()+m+1}))
			r=m;
		else
			l=m+1;
		// ask.clear(); artykmax
	}
	return A[l];
}

// int main(){
// 	int n=5;
// 	vector<pii> v;
// 	v.pb({1, 2}), v.pb({1, 3}), v.pb({2, 4}), v.pb({4, 5});
// 	int mine=findEgg(5, v);
// 	wr;
// 	printf("%d\n", mine);
// 	if(select==mine)
// 		puts("Yay.");
// 	else
// 		puts("Never mind.");
// 	return 0;
// }
// 

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