Submission #476593

#	Time	Username	Problem	Language	Result	Execution time	Memory
476593		lovrot	Easter Eggs (info1cup17_eastereggs)	C++11	0 / 100	14 ms	456 KiB

eastereggs

#include <bits/stdc++.h> 
#include "grader.h"

#define X first
#define Y second

using namespace std; 

vector<int> g[1010];
vector<int> half;
vector<int> all; 
vector<int> help;
vector<int> dod;

int have;
bool took[1010];
bool nxt[1010];
bool need[1010];

/*
int egg;

bool query(vector< int > v){ 
	for(int x : v)
		if(x == egg)
			return true;
	return false;
}
*/
bool dfs(int x, int last){ 
	bool out = need[x];

	for(int y : g[x]){ 
		if(y == last) continue;

		out |= dfs(y, x);
	}

	if(out) all.push_back(x);

	return out;
}

void fix(){ 	
	dod.clear();
	memset(need, 0, sizeof(need));

	for(int x : all)
		need[x] = true;

	int start = all[0];

	all.clear(); 
	dfs(start, -1);

	//for(int x : dod)	
	//	all.push_back(x);
}

void findHalf(int x, int par){ 
	if(have == 0)
		return;

	if(took[x]){
		nxt[x] = true;
		half.push_back(x);

		have--;
	}

	for(int y : g[x]){ 
		if(y == par) 
			continue;

		findHalf(y, x);
	}
} 

int findEgg (int N, vector< pair< int, int > > graf ){ 

	memset(took, 0, sizeof(took));
	all.clear(); 
	half.clear();
	help.clear();
	dod.clear();
	have = 0;
	memset(nxt, false, sizeof(nxt));
	memset(need, false, sizeof(need));

	for(int i = 0; i < 1010; i++)
		g[i].clear();

	for(int i = 0; i < N - 1; i++){ 
		int x = graf[i].X;
		int y = graf[i].Y;

		g[x].push_back(y);
		g[y].push_back(x);
	
		if(!took[x]){ 
			all.push_back(x);
			took[x] = true; 
		}
		if(!took[y]){ 
		 	all.push_back(y);
		 	took[y] = true;
		}
	}

	int ret = -1;

	while(all.size() > 1){ 
		//for(int x : all)	cout << x << " ";

		fix();

		//cout << "\n";

		//for(int x : all) cout << x << " "; 

		//cout << "\n";

		have = N / 2;
		
		half.clear();
		memset(nxt, false, sizeof(nxt));

		findHalf(all[0], -1);

		//for(int x : half)	cout << x << " half \n";

		int ans = query(half);

		//cout << ans << " ans to the query\n";

		if(ans == 1){ 
			N /= 2;
		}
		else{ 
			if(ans == -1){ 
				all.clear();
				break;
			}
			N = N - N / 2;
		}

		help.clear();

		for(int x : all){ 
			if(took[x] and nxt[x] == ans) 
				help.push_back(x);
			else 
				took[x] = false;
		}
		all.clear();

		for(int x : help){ 
			//cout << x << " took to the nxt query\n";
			all.push_back(x);
		}
	}

	if(all.size())
		 ret = all[0];

	return ret;
}

/*
int main(){ 
for(int j = 0; j < 3; j++){
	int m;
	cout << "num. of nodes\n";
 
	cin >> m;
 
	cout << "easter egg\n";
	cin >> egg;
 
	vector< pair<int, int> > inp;
 
	for(int i = 0; i < m - 1; i++){ 
		int a, b;
		cin >> a >> b;
 
		inp.push_back({a, b});
	}
	
	cout << findEgg(m, inp);
}
	return 0;	

} */

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