oj.uz

Submission #475728

# Submission time Handle Problem Language Result Execution time Memory
475728 2021-09-23T21:17:50 Z lovrot Easter Eggs (info1cup17_eastereggs) C++11
0 / 100
 2 ms 456 KB 
#include <bits/stdc++.h> 
#include <unordered_set>
#include "grader.h"
 
#define X first
#define Y second
 
using namespace std; 
 
vector<int> g[530];
vector<int> half;
vector<int> all; 
vector<int> help;
 
int have;
bool took[530];
 
//int egg;
 
int query(vector< int > v); /*{ 
	for(int x : v)
		if(x == egg)
			return true;
	return false;
} */
 
void findHalf(int x){ 
	if(have == 0)
		return;
 
	took[x] = true;
	half.push_back(x);
 
	have--;
	for(int y : g[x]){ 
		if(took[y] == true) 
			continue;
 
		findHalf(y);
	}
} 
 
int findEgg (int n, vector< pair< int, int > > graf ){ 
	memset(took, 0, sizeof(took));
 
	for(int i = 0; i <= n; 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;
		}
	}
	
	memset(took, false, sizeof(took));
 
	while(all.size() > 1){ 
		have = n / 2;
		half.clear();
 
		findHalf(all[0]);
 
		int ans = query(half);
 
		if(ans){ 
			n /= 2;
		}
		else{ 
			n = n - n / 2;
		}
 
		help.clear();
		for(int x : all){ 
			if(took[x] == ans)
				help.push_back(x);
		}
 
		all.clear();
		for(int x : help){
			took[x] = false;
			all.push_back(x);
		}
	}
 
	return all[0];
}
/*
int main(){ 
	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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 456 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 456 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 456 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -