Submission #731812

#	Time	Username	Problem	Language	Result	Execution time	Memory
731812		sentheta	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	21 ms	356 KiB

eastereggs

#include "grader.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const int N = 515;

int n;
V<int> adj[N];

int tot = 0, cnt = 0;
V<int> v;
bool ans[N], inv[N];
void dfs(int x=1,int par=-1){
	if(cnt == tot/2) return;
	cnt += ans[x];
	v.push_back(x);

	for(int y : adj[x]) if(y!=par){
		dfs(y, x);
	}
}

int findEgg(int _n,V<pii> edgs){
	n = _n;
	// dbg(n);
	rep(i,1,n+1){
		adj[i].clear();
		ans[i] = 1;
	}

	for(auto[u,v] : edgs){
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	tot = n;
	while(1){
		cnt = 0;
		v.clear();
		dfs();

		// for(int x : v) cout << x << " ";
		// cout << nl;

		// dbg(tot);
		if(tot==1){
			rep(i,1,n+1) if(ans[i]) return i;
			assert(0);
		}
		// if(v.size()==1) return v[0];

		if(query(v)){
			rep(i,1,n+1) inv[i] = 0;
			for(int x : v) inv[x] = 1;

			rep(i,1,n+1){
				ans[i] &= inv[i];
			}
			tot = tot/2;
		}
		else{
			for(int x : v) ans[x] = 0;
			tot -= tot/2;
		}
	}
}

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