제출 #1325939

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325939		Bzslayed	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	508 KiB

eastereggs

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

using namespace std;

vector<int> v;
vector<int> adj[600];
void dfs(int x, int par){
    v.push_back(x);
    for (auto it : adj[x]){
        if (it != par) dfs(it, x);
    }
}

int findEgg(int N, vector<pair<int, int>> bridges){
    v.clear();
    for (int i=1; i<=N; i++) adj[i].clear();
    for (auto [x, y] : bridges) adj[x].push_back(y), adj[y].push_back(x);
    
    v.push_back(1e9);
    dfs(1, -1);
    int lo = 1, hi = N, ans = N+1;
    while (lo < hi){
        int mid = (lo+hi)>>1;
        vector<int> isl;
        for (int i=1; i<=mid; i++) isl.push_back(v[i]);
        int res = query(isl);
        if (res == 0) lo = mid+1;
        else hi = mid;
    }

    ans = v[lo];
    return ans;
}

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