제출 #1141515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141515		Maaxle	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	504 KiB

eastereggs

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

#define range(it, a, b) for (ll it = a; it < b; it++)
#define invr(it, a, b) for (ll it = a; it >= b; it--)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define ld long double
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue 
#define ptr(A) shared_ptr<A>
#define v(x) vector<x>

using namespace std;

v(v(int)) adj;
v(int) euler;

void euler_tour(ll i, ll p) {
    euler.push_back(i);

    for (int k : adj[i]) {
        if (k == p)
            continue;
        euler_tour(k, i);
    }
}

int findEgg (int N, vector < pair < int, int > > bridges) {
    adj.clear();
    adj.resize(N+1);

    for (auto it : bridges) {
        adj[it.first].push_back(it.second);
        adj[it.second].push_back(it.first);
    }

    euler.clear();
    euler_tour(1, 0);

    int l = 0, r = N-1;
    while (l < r) {
        int m = (l + r) / 2;

        v(int) st;
        range(j, 0, m+1) 
            st.push_back(euler[j]);
        if (query(st)) 
            r = m;
        else l = m+1;
    }
    return euler[l];
}

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