제출 #1146776

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

eastereggs

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


using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

using ll = long long;

template<typename... T>
void see(T&... args) { ((cin >> args), ...);}
#define seea(a , x , y) for(int i = x; i < y; i++){cin >> a[i];}
#define sees(s , n) for(int i = 0;i < n; i++){int x; cin >> x; s.insert(x);}
#define seev(v , n) for(int i = 0;i < n; i++){int x; cin >> x; v.push_back(x);}
#define ub(a, x) upper_bound(all(a), x)
#define lb(a, x) lower_bound(all(a), x)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define pii pair<int , int>
#define sz(x) (int)x.size()
#define pq priority_queue
#define vec vector
#define arr array

int n;

vec<vec<int>> g;

int findEgg (int N, vector < pair < int, int > > bridges)
{
    n = N;
    g.resize(n);
    for (auto [x , y] : bridges){
        x -- , y -- ;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vec<int> pf;
    queue<int> q;
    vec<int> us(n , false);
    us[0] = true;
    q.push(0);
    while(!q.empty()){
        int v = q.front(); 
        q.pop();
        pf.push_back(v + 1);
        for (auto to : g[v])
            if (!us[to])
                q.push(to) , us[to] = true;
    }
    int l = 0 , r = n - 1;
    while(l < r){
        int m = (l + r) >> 1;
        vec<int> ch(pf.begin() , pf.begin() + m + 1);
        if (query(ch))
            r = m;
        else 
            l = m + 1;
    }
    return pf[l];
}

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