oj.uz

Submission #731812

# Submission time Handle Problem Language Result Execution time Memory
731812 2023-04-28T03:07:39 Z sentheta Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 21 ms 356 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Number of queries: 4
2 Correct 1 ms 208 KB Number of queries: 4
3 Correct 1 ms 208 KB Number of queries: 4
4 Correct 1 ms 208 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 348 KB Number of queries: 8
2 Correct 16 ms 336 KB Number of queries: 9
3 Correct 21 ms 356 KB Number of queries: 9
4 Correct 16 ms 352 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 336 KB Number of queries: 9
2 Correct 20 ms 336 KB Number of queries: 9
3 Correct 15 ms 336 KB Number of queries: 9
4 Correct 15 ms 352 KB Number of queries: 9