oj.uz

Submission #98557

# Submission time Handle Problem Language Result Execution time Memory
98557 2019-02-24T08:00:56 Z mohammedehab2002 Easter Eggs (info1cup17_eastereggs) C++11
100 / 100
 32 ms 384 KB 
#include <iostream>
#include "grader.h"
#include <vector>
using namespace std;
vector<int> v[515],t;
void dfs(int node,int p)
{
	t.push_back(node);
	for (int u:v[node])
	{
		if (u!=p)
		dfs(u,node);
	}
}
bool check(int m)
{
	vector<int> tmp;
	for (int i=0;i<=m;i++)
	tmp.push_back(t[i]);
	return query(tmp);
}
int findEgg(int n,vector<pair<int,int> > e)
{
	if (t.empty())
	{
		for (auto p:e)
		{
			v[p.first].push_back(p.second);
			v[p.second].push_back(p.first);
		}
		dfs(1,0);
	}
	int st=0,en=n-1;
	while (st!=en)
	{
		int mid=(st+en)/2;
		if (check(mid))
		en=mid;
		else
		st=mid+1;
	}
	return t[st];
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Number of queries: 4
2 Correct 3 ms 384 KB Number of queries: 4
3 Correct 1 ms 384 KB Number of queries: 4
4 Correct 4 ms 256 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 256 KB Number of queries: 8
2 Correct 10 ms 360 KB Number of queries: 9
3 Correct 31 ms 324 KB Number of queries: 9
4 Correct 32 ms 256 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 384 KB Number of queries: 9
2 Correct 21 ms 256 KB Number of queries: 9
3 Correct 16 ms 360 KB Number of queries: 9
4 Correct 27 ms 256 KB Number of queries: 9