Submission #1277466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277466		icyalmond	Easter Eggs (info1cup17_eastereggs)	C++20	87 / 100	8 ms	532 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;
bool vi[515];

void DFS(int node, int pre)
{
    vi[node] = 1;
    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(), vi[i] = 0;
    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);
    }
    for (int i = 1; i <= N; i++)
    {
        if (vi[i] == 0) DFS(i, i);
    }
    int le = 1, ri = N, ans = 0;
    while (le <= ri)
    {
        int mi = le + ri >> 1;
        vector <int> v(tour.begin(), tour.begin() + mi);
        if (query(v))
        {
            ans = tour[mi - 1];
            ri = mi - 1;
        }
        else le = mi + 1;
    }
    return ans;
}

//coded by icyalmond

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