제출 #1285821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285821		sunflower	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	8 ms	496 KiB

eastereggs

#ifndef SUN
#include "grader.h"
#endif // SUN

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

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)

#ifdef SUN
bool query(vector<int> islands) {
    return true;
}
#endif // SUN

#define MAX_NODE 520
vector<int> adj[MAX_NODE + 2];

vector<int> euler;

void dfs(int u, int par = -1) {
    euler.push_back(u);

    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
    }
}

int findEgg(int n, vector <pair <int, int>> edges) {
    FOR(i, 1, n) adj[i].clear();
    euler.clear();

    for (const pair <int, int> &e : edges) {
        int u = e.first, v = e.second;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1);

    int l = 1, r = n, g, vt = -1;
    while (l < r) {
        g = (l + r) >> 1;
        vector<int> ask;
        for (int i = 0; i < g; ++i) ask.push_back(euler[i]);

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

    return euler[r - 1];
}

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