제출 #1336197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1336197		moonbaek	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	2 ms	520 KiB

eastereggs

#include <bits/stdc++.h>
using namespace std;

int query(vector<int> islands);

int findEgg(int N, vector<pair<int,int>> bridges){

    vector<vector<int>> adj(N+1);
    for(auto [u,v] : bridges){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> tin(N+1), tout(N+1), euler;
    euler.reserve(N);

    function<void(int,int)> dfs = [&](int u,int p){
        tin[u] = euler.size();
        euler.push_back(u);

        for(int v:adj[u])
            if(v!=p)
                dfs(v,u);

        tout[u] = euler.size()-1;
    };

    dfs(1,0);

    int l = 0, r = N-1;

    while(l < r){

        int mid = (l+r)/2;

        vector<int> ask;

        for(int i=l;i<=mid;i++)
            ask.push_back(euler[i]);

        if(query(ask))
            r = mid;
        else
            l = mid+1;
    }

    return euler[l];
}

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