oj.uz

Submission #389248

# Submission time Handle Problem Language Result Execution time Memory
389248 2021-04-14T01:39:31 Z Kevin_Zhang_TW Easter Eggs (info1cup17_eastereggs) C++17
81 / 100
 28 ms 328 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) {
		int S = 0, R = -1;
		for (int i = 1;i <= N;++i) {
			if (!ban[i]) {
				R = i;
				++S;
			}
		}
		if (S == 1) return R;
		if (S == 2) {
			if (query({R})) return R;
			for (int i = 1;i <= N;++i)
				if (!ban[i]) return i;
			assert(false);
		}

		DE(S, R);

		// I need to clear thing in edge

		function<int(int,int)> dfs = [&](int x, int lst) {
			sz[x] = 1;
			for (int u : edge[x]) if (u != lst)
				sz[x] += dfs(u, x);
			return sz[x];
		};
		function<int(int,int)> get_cen = [&](int x, int lst) {
			for (int u : edge[x]) if (u != lst)
				if (sz[u] * 2 > S)
					return get_cen(u, x);
			return x;
		};

		vector<int> con;

		function<void(int,int)> get_child = [&](int x, int lst) {
			con.pb(x);
			for (int u : edge[x]) if (u != lst)
				get_child(u, x);
		};

		dfs(R, R);
		int rt = get_cen(R, R);
		dfs(rt, rt);

		sort(AI(edge[rt]), [&](int a, int b) {
			return sz[a] > sz[b];
		});

		int sum = 0, mid = (S-1) / 2;

		con.pb(rt);

		for (int u : edge[rt]) {
			int ns = sum + sz[u];
			if (abs(ns - mid) >= abs(sum - mid)) continue;
			get_child(u, rt);
			sum += sz[u];
		}

		DE(S, sum);

		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;
		}

		ban[rt] = false;

		for (int i = 1;i <= N;++i) {
			int sz = 0;
			for (int u : edge[i])
				if (!ban[u])
					edge[i][sz++] = u;
			edge[i].resize(sz);
		}

	}
	assert(false);
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
eastereggs.cpp:48:3: note: in expansion of macro 'DE'
   48 |   DE(S, R);
      |   ^~
eastereggs.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
eastereggs.cpp:92:3: note: in expansion of macro 'DE'
   92 |   DE(S, sum);
      |   ^~

Subtask #1
32.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 200 KB Number of queries: 5
2 Partially correct 2 ms 200 KB Number of queries: 6
3 Partially correct 1 ms 200 KB Number of queries: 5
4 Partially correct 1 ms 204 KB Number of queries: 5

Subtask #2
34.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 200 KB Number of queries: 9
2 Partially correct 13 ms 328 KB Number of queries: 10
3 Partially correct 20 ms 328 KB Number of queries: 11
4 Partially correct 17 ms 328 KB Number of queries: 10

Subtask #3
15.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 19 ms 328 KB Number of queries: 10
2 Partially correct 28 ms 328 KB Number of queries: 11
3 Partially correct 17 ms 328 KB Number of queries: 11
4 Partially correct 16 ms 328 KB Number of queries: 10