제출 #1194336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194336		a0ms1n	Easter Eggs (info1cup17_eastereggs)	C++20	66 / 100	11 ms	504 KiB

eastereggs

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

using namespace std;

vector<vector<int>> adjL;
vector<int> path;

void dfs(int u,int p=-1){
    path.push_back(u);
    for(int v:adjL[u]){
        if(v==p)continue;
        dfs(v,u);
    }
}

bool cando(int x){
    vector<int> ans;
    for(int i=0;i<=x;i++)ans.push_back(path[i]);
    return query(ans);
}

int findEgg (int N, vector < pair < int, int > > bridges){
    path.clear();
    adjL.clear();
    adjL.resize(N+1);
    //cout<<"HEY\n";
    for(const auto &[u,v]:bridges){
        adjL[u].push_back(v);
        adjL[v].push_back(u);
    }
    dfs(1);
    int l=0,r = path.size()-1;
    for(int b=(r>1?r/2:1);b>0;b>>=1ll){
        while(r-b>=l && cando(r-b))r-=b;
    }
    return path[r];
}

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