Submission #762476

#	Time	Username	Problem	Language	Result	Execution time	Memory
762476		beepbeepsheep	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	14 ms	360 KiB

eastereggs

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

using namespace std;

const int maxn=520;
vector<short> adj[maxn];
vector<short> v;
int ptr;
vector<int> q;
void dfs(short x, short p){
    v.emplace_back(x);
    for (auto u:adj[x]){
        if (u==p) continue;
        dfs(u,x);
    }
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
    for (int i=0;i<maxn;i++) adj[i].clear();
    v.clear();
    q.clear();
    ptr=0;
    for (auto [u,v]:bridges){
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfs(1,-1);
    int l=0,r=N,m;
    while (l!=r-1){
        m=(l+r)>>1;
        while (ptr<m){
            q.emplace_back(v[ptr++]);
        }
        while (ptr>m){
            q.pop_back();
            ptr--;
        }
        if (query(q)) r=m;
        else l=m;
    }
    return v[l];
}

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