oj.uz

Submission #389259

# Submission time Handle Problem Language Result Execution time Memory
389259 2021-04-14T01:46:05 Z Kevin_Zhang_TW Easter Eggs (info1cup17_eastereggs) C++17
81 / 100
 100 ms 1352 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);

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


//		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: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:124:3: note: in expansion of macro 'DE'
  124 |   DE(S, sum);
      |   ^~
eastereggs.cpp:81:7: warning: unused variable 'sum' [-Wunused-variable]
   81 |   int sum = 0, mid = (S-1) / 2;
      |       ^~~

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: 5
3 Partially correct 2 ms 200 KB Number of queries: 5
4 Partially correct 1 ms 200 KB Number of queries: 5

Subtask #2
34.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 584 KB Number of queries: 9
2 Partially correct 38 ms 968 KB Number of queries: 10
3 Partially correct 65 ms 1224 KB Number of queries: 11
4 Partially correct 97 ms 1224 KB Number of queries: 10

Subtask #3
15.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 66 ms 1352 KB Number of queries: 10
2 Partially correct 67 ms 1352 KB Number of queries: 11
3 Partially correct 68 ms 1352 KB Number of queries: 11
4 Partially correct 100 ms 1352 KB Number of queries: 10