oj.uz

답안 #389322

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
389322 2021-04-14T02:58:02 Z rk42745417 Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 16 ms 456 KB 
#include <bits/stdc++.h>
#include "grader.h"
//#include "grader.cpp"
using namespace std;

#define EMT ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
const double EPS = 1e-9;

vector<vector<int>> edge;
vector<int> sz;
vector<int> que;
vector<bool> ok;
vector<bool> is;
int _n;

void init(int n) {
	_n = n;
	edge.clear();
	sz.clear();
	is.clear();
	ok.clear();
	edge.resize(n + 1);
	sz.resize(n + 1);
	is.resize(n + 1);
	ok.resize(n + 1);
}
int dfs(int u, int p) {
	sz[u] = 1;
	for(int v : edge[u])
		if(v != p && ok[v])
			sz[u] += dfs(v, u);
	return sz[u];
}
int centroid(int u, int p, int n) {
	for(int v : edge[u])
		if(v != p && ok[v] && sz[v] > n / 2)
			return centroid(v, u, n);
	return u;
}
void go(int u, int p) {
	que.push_back(u);
	is[u] = 1;
	for(int v : edge[u])
		if(v != p && ok[v])
			go(v, u);
}
int solve(int u) {
	for(int a : que) {
		is[a] = 0;
		//cerr << "removing " << a << " from que\n";
	}
	que.clear();

	int n = dfs(u, u);
	if(n == 1)
		return u;
	//cerr << u << ' ' << sz[u] << '\n';
	u = centroid(u, u, n);
	//cerr << u << '\n';
	dfs(u, u);
	assert(sz[u] == n);
	
	que.push_back(u);
	is[u] = 1;
	int cur = 0;
	for(int v : edge[u]) {
		//cerr << "owo " << sz[v] << ' ' << ok[v] << cur + sz[v] << ' ' << n / 2 << '\n';
		if(ok[v] && cur + sz[v] <= n / 2)
			go(v, u), cur += sz[v];
	}
	if(n == 2) {
		int x = que.back();
		que.pop_back();
		if(query(que))
			return que[0];
		else
			return x;
	}
	//cerr << cur << '\n';

	assert(!que.empty());
	int w = query(que);
	if(w) {
		for(int i = 1; i <= _n; i++)
			if(!is[i]) {
				ok[i] = 0;
				//cerr << "deletea " << i << '\n';
			}
		//cerr << "owo " << que[0] << '\n';
		return solve(u);
	}
	else {
		//cerr << "xdd " << que.size() << '\n';
		for(int a : que) {
			ok[a] = 0;
			//cerr << "deleteb " << a << '\n';
		}
		for(int v : edge[u])
			if(!is[v])
				return solve(v);
	}
	assert(0);
	return 0;
}
int findEgg(int n, vector<pair<int, int>> edges) {
	init(n);
	
	//cerr << "here\n";
	for(int i = 1; i <= n; i++)
		ok[i] = 1;
	//cerr << "here\n";
	for(const auto &[a, b] : edges)
		edge[a].push_back(b), edge[b].push_back(a);
	//cerr << "here\n";
	return solve(1);
}

Subtask #1
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 324 KB Number of queries: 5
2 Runtime error 1 ms 424 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 200 KB Number of queries: 9
2 Runtime error 1 ms 456 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 16 ms 328 KB Number of queries: 10
2 Runtime error 1 ms 456 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -