제출 #374769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
374769		Alex_tz307	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	28 ms	512 KiB

eastereggs

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

using namespace std;

const int NMAX = 515;
vector<int> G[NMAX], dfs_pref;

void dfs(int u, int parent) {
    dfs_pref.emplace_back(u);
    for(const int &v : G[u])
        if(v != parent)
            dfs(v, u);
}

void Clear(int N) {
    for(int u = 1; u <= N; ++u)
        G[u].clear();
    dfs_pref.clear();
    dfs_pref.emplace_back(0);
}

bool check(int poz) {
    vector<int> ask;
    for(int i = 1; i <= poz; ++i)
        ask.emplace_back(dfs_pref[i]);
    return query(ask);
}

int findEgg(int N, vector<pair<int,int>> bridges) {
    Clear(N);
    for(int i = 0; i < N - 1; ++i) {
        int u, v;
        tie(u, v) = bridges[i];
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1, 0);
    int st = 1, dr = N - 1, ans = N;
    while(st <= dr) {
        int mid = (st + dr) >> 1;
        if(check(mid)) {
            ans = mid;
            dr = mid - 1;
        }
        else
            st = mid + 1;
    }
    return dfs_pref[ans];
}

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