Submission #1275601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275601		nicolo_010	Easter Eggs (info1cup17_eastereggs)	C++20	87 / 100	9 ms	500 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

vector<int> euler;
vector<vector<int>> adj;

void dfs(int n, int p=-1) {
    euler.push_back(n);
    for (auto x : adj[n]) {
        if (x==p) continue;
        dfs(x, n);
    }
}

int findEgg (int N, vector < pair < int, int > > bridges) {
    adj.resize(N);
    euler.clear();
    for (int i=0; i<N-1; i++) {
        int a = bridges[i].first;
        int b = bridges[i].second;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(0);
    int n = euler.size();
    int l = 0, r = n-1;
    int ans = 0;
    while (l <= r) {
        int m = (l+r+1)/2;
        vector<int> ask;
        for (int i=0; i<n; i++) {
            if (i<=m) ask.push_back(euler[i]+1);
        }
        int q = query(ask);
        if (q == 1) {
            r = m-1;
        }
        else {
            l = m+1;
            ans = m+1;
        }
    }
    int anss = euler[ans]+1;
    for (int i=0; i<N; i++) {
        adj[i].clear();
    }
    adj.clear();
    return anss;
}

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