Submission #1285816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285816		sunflower	Easter Eggs (info1cup17_eastereggs)	C++17	87 / 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)) vt = g, r = g - 1;
        else l = g + 1;
    }

    return euler[vt - 1];
}

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