Submission #1226498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226498		kokoxuya	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	0 ms	484 KiB

eastereggs

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
int curr;
#define pb push_back

void dfs(int cn, vector<int>&preorder, vector<vector<int>>&adjlist)
{
	preorder[cn]=++curr;
	for(int to:adjlist[cn])
	{
		if(preorder[to]!=0)continue;
		dfs(to,preorder,adjlist);
	}
}


int findEgg (int n, vector<pair<int,int>>bridges)
{
    vector<int>preorder(n+1,0);
    vector<vector<int>>adjlist(n+1);
    for(int a=0;a<(n-1);a++)
    {
		int t1=bridges[a].first,t2=bridges[a].second;
		adjlist[t1].pb(t2);
		adjlist[t2].pb(t1);
	}
	
	curr=0;
	dfs(1,preorder,adjlist);
	
	int hi=n,lo=1,mid,ans;
	while(hi>=lo)
	{
		mid=(hi+lo)/2;
		vector<int>queset;
		for(int a=lo;a<=mid;a++){queset.pb(a);}
		if(query(queset))
		{
			ans=mid;
			hi=mid-1;
		}
		else
		{
			lo=mid+1;
		}
	}
	return ans;
}

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