제출 #389272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
389272		Kevin_Zhang_TW	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	33 ms	464 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

// int query(vector<int> h) 

using namespace std;

int findEgg (int N, vector < pair < int, int > > bridges) {

	vector<int> sz(N+1);
	vector<bool> ban(N+1);
	vector<vector<int>> edge(N+1);

	for (auto [a, b] : bridges)
		edge[a].pb(b), edge[b].pb(a);

	while (true) {
		vector<int> con;
		int SZ = 0, cnt = 0;
		for (int i = 1;i <= N;++i) if (!ban[i])
			++SZ;
		if (SZ == 1) for (int i = 1;i <= N;++i) if (!ban[i])
			return i;

		function<void(int,int)> dfs = [&](int x, int lst) {
			if (cnt == SZ / 2) return;
			con.pb(x);
			cnt += !ban[x];
			for (int u : edge[x]) if (u != lst) {
				dfs(u, x);
			}
		};

		dfs(1, 1);

		if (query(con)) {
			vector<bool> good(N+1);
			for (int u : con) good[u] = true;
			for (int i = 1;i <= N;++i)
				if (!good[i]) ban[i] = true;
		}
		else for (int u : con) ban[u] = true;
	}
	assert(false);
}

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