Submission #822975

#	Time	Username	Problem	Language	Result	Execution time	Memory
822975		Darren0724	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	16 ms	392 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;
vector<int> v;
vector<vector<int>> adj;
void dfs(int k,int pa){
    v.push_back(k);
    for(int j:adj[k]){
        if(j==pa)continue;
        dfs(j,k);
    }
}
int findEgg (int n, vector<pair<int,int>> bridges)
{
    v.clear();
    adj.clear();
    adj.resize(n+1);
    for(auto [a,b]:bridges){
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,1);
    int l=0,r=n;
    while(r-l>1){
        int m=(l+r)>>1;
        vector<int> a(v.begin(),v.begin()+m);
        if(query(a)){
            r=m;
        }
        else{
            l=m;
        }
    }
    return v[l];
    
}

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