제출 #1139587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139587		KasymK	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	1 ms	472 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];
int A[N], id;
// int select=4;

void dfs(int x, int pr=-1){
	A[++id]=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){
	tr(it, v)
	adj[it->ff].pb(it->ss), adj[it->ss].pb(it->ff);	
	dfs(1);
	int l=1, r=n, answer=-1;
	vector<int> ask;
	while(l<=r){
		int m=(l+r)>>1;
		for(int i = 1; i <= m; ++i)
			ask.pb(A[i]);
		if(query(ask))
			r=m-1, answer=m;
		else
			l=m+1;
		ask.clear();
	}
	assert(~answer);
	return A[answer];
}

// 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==A[mine])
// 		puts("Yay.");
// 	else
// 		puts("Never mind.");
// 	return 0;
// }

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