Submission #1226713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226713		jellybean	Easter Eggs (info1cup17_eastereggs)	C++20	40 / 100	21 ms	580 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;

int dfs(int cn, map<int,int>&preorder, map<int, vector<int>>&adjlist, int curr, vector<int>&corrfrom)
{
	preorder[cn]=++curr;
	corrfrom[preorder[cn]]=cn;
	for(int to:adjlist[cn])
	{
		if(preorder.count(to))continue;
		curr=dfs(to,preorder,adjlist,curr,corrfrom);
	}
	return curr;
}


int findEgg (int N, vector<pair<int,int>>bridges)
{
    map<int,int>preorder;map<int,vector<int>>adjlist;
    vector<int>corrfrom(N+1);
    for(int a=0;a<(N-1);a++)
    {
		int t1=bridges[a].first,t2=bridges[a].second;
		adjlist[t1].push_back(t2);
		adjlist[t2].push_back(t1);
	}

	dfs(1,preorder,adjlist,0,corrfrom);
	
	int hi=N,lo=1,mid;
	while(hi>lo+1)
	{
		mid=(hi+lo)/2;
		vector<int>queset;
		for(int a=1;a<=mid;a++){queset.push_back(corrfrom[a]);}
		if(query(queset))
		{
			hi=mid;
		}
		else
		{
			lo=mid;
		}
	}
	return corrfrom[hi];
}

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