Submission #1283760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283760		Jawad_Akbar_JJ	Easter Eggs (info1cup17_eastereggs)	C++17	81 / 100	11 ms	332 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], adj[M], False[M], cur, Again;

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

void dfs1(int u, int p){
	for (int i : nei[u]){
		if (i == p or Block[i])
			continue;
		dfs1(i, u);
	}
	if (adj[u] == 1 and False[u])
		Block[u] = Again = 1;
}

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++;
	Again = 1;
	while (Again){
		Again = 0;
		dfs0(u, u);
		dfs1(u, u);
		if (Block[u]){
			for (int i : nei[u]){
				if (!Block[i]){
					u = i;
					break;
				}
			}
		}
	}

	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, ncld;
	vc.clear();;
	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 : nei[c]){
		if (!Block[i] and seen[i] != cur)
			ncld.push_back(i);
	}

	for (int i : cld)
		Add(i, c);
	if (vc.size() * 2 == ch[c]){
		vc.clear();
		swap(cld, ncld);
		for (int i : cld)
			Add(i, c);
	}

	vc.push_back(c);
	int ans = query(vc);
	if (ans == 1){
		for (int i : ncld)
			Block[i] = 1;
	}
	else{
		for (int i : cld)
			Block[i] = 1;
		False[c] = 1;		
	}
	return dfs(c);
}

int findEgg(int n, vector<pair<int, int>> vec){
	for (int i=0;i<vec.size();i++){
		nei[vec[i].first].push_back(vec[i].second);
		nei[vec[i].second].push_back(vec[i].first);
	}

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

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