Submission #1283705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283705		Jawad_Akbar_JJ	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	1 ms	488 KiB

eastereggs

#include <iostream>
#include <vector>
#include "grader.h"

using namespace std;
const int M = 550;
vector<int> nei[M], vc;
int ch[M], Block[M], Lst[M], seen[M], cur;

void dfs0(int u, int p){
	ch[u] = 1;
	for (int i : nei[u]){
		if (i == p or Block[i])
			continue;
		dfs0(i, u);
		ch[u] += ch[i];
	}
}

void Add(int u, int p){
	for (int i : nei[u]){
		if (i == p or Block[i])
			continue;
		Add(i, u);
	}
	vc.push_back(u);
}

int findCent(int u, int p, int rtSz){
	for (int i : nei[u]){
		if (i != p and !Block[i] and ch[i] * 2 > rtSz)
			return findCent(i, u, rtSz);
	}
	return u;
}

int dfs(int u){
	cur++;
	dfs0(u, u);
	if (ch[u] == 1)
		return u;

	if (ch[u] == 2){
		for (int i : nei[u]){
			if (Block[i])
				continue;
			if (query({u}))
				return u;
			return i;
		}
	}

	int c = findCent(u, u, ch[u]);
	dfs0(c, c);

	for (int i=1;i<=ch[c];i++)
		Lst[i] = -1;

	for (int i : nei[c]){
		if (Block[i])
			continue;
		for (int j=ch[c];j>=ch[i];j--){
			if (Lst[j] == -1 and Lst[j - ch[i]] != -1)
				Lst[j] = i;
		}
	}

	vector<int> cld;
	vc = {c};
	for (int i=ch[c]-1;i>=0;i--){
		if (Lst[i] != -1 and i * 2 < ch[c]){
			while (i != 0)
				cld.push_back(Lst[i]), seen[Lst[i]] = cur, i -= ch[Lst[i]];
		}
	}

	for (int i : cld)
		Add(i, c);

	bool ans = query(vc);
	for (int i : nei[u])
		if ((seen[i] != cur) == ans)
			Block[i] = 1;
	return dfs(c);
}

int findEgg(int n, vector<pair<int, int>> vec){
	for (auto [a, b] : vec){
		nei[a].push_back(b);
		nei[b].push_back(a);
	}

	int ans = dfs(1);
	for (int i=1;i<=n;i++){
		nei[i].clear();
		Block[i] = 0;
	}
	return ans;
}

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20