Submission #1259428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259428		truongdz_top12	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	508 KiB

eastereggs

#include "grader.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>adj[513],order;
void DFS(int u,int f)
{
    order.push_back(u);
    for(auto&v:adj[u])
        if(v!=f)
            DFS(v,u);
}
int findEgg(int N,vector<pair<int,int>>bridges)
{
    order.clear();
    for(int u=1;u<=N;++u)
        adj[u].clear();
    for(auto&[u,v]:bridges)
    {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    DFS(1,0);
    int l=0,r=N-1;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(query(vector<int>(order.begin(),order.begin()+mid))==1)
            r=mid-1;
        else
            l=mid;
    }
    return order[l];
}

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