제출 #1283741

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283741		Jawad_Akbar_JJ	Easter Eggs (info1cup17_eastereggs)	C++17	81 / 100	11 ms	420 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, ncld;
	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 : nei[c]){
		if (!Block[i] and seen[i] != cur)
			ncld.push_back(i);
	}

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

	int ans = query(vc);
	if (ans == 1){
		for (int i : ncld)
			Block[i] = 1;
		return dfs(c);
	}
	else{
		for (int i : cld)
			Block[i] = 1;
		if (ncld.size() == 1)
			Block[c] = 1, c = ncld[0];
		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] = 0;
	}
	return ans;
}

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