Submission #1180120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180120		ZeroCool	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	512 KiB

eastereggs

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



using namespace std;
const int N = 600;


vector<int> g[N];
vector<int> ord;

void dfs(int x,int p){
    ord.push_back(x);
    for(auto u: g[x]){
        if(u != p)dfs(u, x);
    }
}

int findEgg (int n, vector < pair < int, int > > e){
    for(int i = 1;i <= n;i++)g[i].clear();
    ord.clear();
    for(auto [a, b]: e){
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 1);
    int lo = -1, hi = n - 1;
    //for(auto u: ord)cout<<u<<" ";
    //cout<<'\n';
    while(hi - lo > 1){
        int mid = (lo + hi) / 2;
        vector<int> q;
        for(int i = 0;i <= mid;i++)q.push_back(ord[i]);
        if(query(q))hi = mid;
        else lo = mid;
    }
    return ord[hi];
}

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