oj.uz

Submission #243041

# Submission time Handle Problem Language Result Execution time Memory
243041 2020-06-30T08:06:37 Z HachiMinh Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 26 ms 384 KB 
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef vector<int> vct;
vct HMS[600],USS;
void dfs(int u,int pa)
{
	USS.pb(u);
	for(int i=0;i<HMS[u].size();i++)
	{
		int d=HMS[u][i];
		if(d!=pa)
		{
			dfs(d,u);
		}
	}
}
int check(int mid)
{
	vector<int> KMS;
	for(int i=0;i<=mid;i++)
	{
		KMS.pb(USS[i]);
	}
	return query(KMS);
}
int findEgg(int N,vector<pair<int,int> >bridges)
{
	USS.clear();
	for(int i=0;i<N-1;i++)
	{
		int u=bridges[i].fi,v=bridges[i].se;
		HMS[u].pb(v);
		HMS[v].pb(u);
	}
	dfs(1,0);
	int l=0,r=USS.size()-1;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	for(int i=0;i<N+7;i++) HMS[i].clear();
	return USS[l];
}

Compilation message

eastereggs.cpp: In function 'void dfs(int, int)':
eastereggs.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<HMS[u].size();i++)
              ~^~~~~~~~~~~~~~

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Number of queries: 8
2 Correct 19 ms 384 KB Number of queries: 9
3 Correct 20 ms 384 KB Number of queries: 9
4 Correct 24 ms 384 KB Number of queries: 9

Subtask #3
20.0 / 20.0

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