Submission #389263

#	Time	Username	Problem	Language	Result	Execution time	Memory
389263		Kevin_Zhang_TW	Easter Eggs (info1cup17_eastereggs)	C++17	81 / 100	103 ms	1352 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) {
		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);

		vector<vector<int>> dp(N+5, vector<int>(N));

		dp[0][0] = true;

		for (int i = 0;i < edge[rt].size();++i) {
			int u = edge[rt][i];
			dp[i+1] = dp[i];
			for (int j = 0;j < N;++j)
				if (dp[i][j]) 
					dp[i+1][j + sz[u]] = true;
		}

		int ans = 0;

		for (int i = 0;i < S;++i)
			if (dp[edge[rt].size()][i]) {
				if (abs(ans-mid) >= abs(i-mid))
					ans = i;
			}

		for (int i = (int)edge[rt].size() - 1;i >= 0;--i) {
			int u = edge[rt][i];
			if (sz[u] > ans) continue;
			if (dp[i][ ans - sz[u] ]) {
				ans -= sz[u];
				get_child(u, rt);
			}
		}

		assert(ans == 0);

		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 (stderr)

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:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for (int i = 0;i < edge[rt].size();++i) {
      |                  ~~^~~~~~~~~~~~~~~~~
eastereggs.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
eastereggs.cpp:116:3: note: in expansion of macro 'DE'
  116 |   DE(S, sum);
      |   ^~
eastereggs.cpp:81:7: warning: unused variable 'sum' [-Wunused-variable]
   81 |   int sum = 0, mid = (S-1) / 2;
      |       ^~~

• Subtask 1: 32 / 40
• Subtask 2: 34 / 40
• Subtask 3: 15 / 20