Submission #1128272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128272		enzy	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	10 ms	500 KiB

eastereggs

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

using namespace std;
const int maxn=514;
vector<int>v[maxn];
int pre[maxn], lin[maxn], tmp, n;
void dfs(int u){
    tmp++;
    pre[u]=tmp;
    for(auto viz : v[u]){
        if(pre[viz]) continue;
        dfs(viz);
    }
}
bool check(int x){
    vector<int>ask;
    for(int i=1;i<=x;i++) ask.push_back(lin[i]);
    return query(ask);
}
int findEgg (int N,vector<pair<int,int>> bridges){
    n=N;
    tmp=0;
    for(int i=1;i<=n;i++){
        v[i].clear();
        pre[i]=0;
    }
    for(auto p : bridges){
        v[p.first].push_back(p.second);
        v[p.second].push_back(p.first);
    }
    dfs(1);
    for(int i=1;i<=n;i++) lin[pre[i]]=i;
    int l=1, r=n;
    while(l<r){
        int mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    return lin[l];
}

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