oj.uz

Submission #924417

# Submission time Handle Problem Language Result Execution time Memory
924417 2024-02-09T03:23:51 Z Nurislam Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 400 ms 11120 KB 
#include <bits/stdc++.h>
#include "grader.h"
//~ #include "grader.cpp"
using namespace std;
#define pb push_back
int ans = 0;
vector<int> g[200004];
int us[200005], m, ctr;
int dcnt(int pos, int pre){
	int s = 1;
	for(auto to:g[pos]){
		if(us[to] || to == pre)continue;
		s+=dcnt(to, pos);
	}
	return s;
}
int dct(int pos, int pre){
	bool ok = 1;
	int s = 1;
	for(auto to:g[pos]){
		if(us[to] || to == pre)continue;
		int sn = 0;
		sn = dcnt(to, pos);
		if(sn > m/2)ok = 0;
		s+=sn;
	}
	if(s < m/2)ok = 0;
	if(ok)ctr = pos;
	return s;
}
vector<int> re;
void dfs(int pos, int pre){
	re.pb(pos);
	for(int to:g[pos]){
		if(us[to] || to == pre)continue;
		dfs(to, pos);
	}
}
void ctrdec(int pos){
	m = dcnt(pos, -1);
	m = dct(pos, -1);
	us[ctr] = 1;
	ans = ctr;
	for(auto to:g[ctr]){
		re.clear();
		dfs(to, -1);
		if(!query(re))continue;
		ctrdec(to);
	}
}
int findEgg (int n, vector < pair < int, int > > way)
{
	for(auto [u, v]: way){
		g[u].pb(v);
		g[v].pb(u);
	}
	ctrdec(1);
	
	return ans;
}

Subtask #1
0 / 40.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 5720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3034 ms 5720 KB Time limit exceeded
2 Halted 0 ms 0 KB -