oj.uz

Submission #389272

# Submission time Handle Problem Language Result Execution time Memory
389272 2021-04-14T02:02:32 Z Kevin_Zhang_TW Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 33 ms 464 KB 
#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.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 328 KB Number of queries: 8
2 Correct 20 ms 336 KB Number of queries: 9
3 Correct 33 ms 344 KB Number of queries: 9
4 Correct 25 ms 328 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 328 KB Number of queries: 9
2 Correct 22 ms 464 KB Number of queries: 9
3 Correct 24 ms 348 KB Number of queries: 9
4 Correct 25 ms 348 KB Number of queries: 9