제출 #1277496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277496		icyalmond	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	500 KiB

eastereggs

#include "grader.h"
#include <bits/stdc++.h>
#define ii pair <int, int>
#define ll long long
#define llll pair <ll, ll>
#define ld long double
#define el "\n"
#define sp " "
#define fi first
#define se second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define __lcm(a, b) (a / __gcd(a, b) * b)
#define sq(x) (x) * (x)
#define sz(a) (int)(a.size())
using namespace std;

const int INFI = 1e9 + 7; const ll INFL = 2e18 + 7;

vector <int> g[515], tour;

void DFS(int node, int pre)
{
    tour.pub(node);
    for (int i : g[node])
    {
        if (i != pre) DFS(i, node);
    }
}

int findEgg(int N, vector <pair <int, int>> bridges)
{
    for (int i = 1; i <= N; i++) g[i].clear();
    tour.clear();
    for (int i = 0; i < N - 1; i++)
    {
        g[bridges[i].fi].pub(bridges[i].se);
        g[bridges[i].se].pub(bridges[i].fi);
    }
    DFS(1, 1);
    int le = 0, ri = N - 1;
    while (le < ri)
    {
        int mi = le + ri >> 1;
        if (query(vector <int>(tour.begin(), tour.begin() + mi + 1))) ri = mi;
        else le = mi + 1;
    }
    return tour[le];
}

//coded by icyalmond

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