제출 #1141365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141365		aarb_.tomatexd	Easter Eggs (info1cup17_eastereggs)	C++20	87 / 100	10 ms	2920 KiB

eastereggs

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define SZ(x) ((int)(x).size())

//binaria
vector<int>adj[100000];
int tin[100000], node[100000];

int t = 0;

void dfs(int u, int p){
    tin[u]= ++t;
    node[t] = u;
    for(auto v: adj[u])
        if(v!= p) 
            dfs(v, u);
}

int findEgg(int N,vector<pair<int, int>>bridges){
    for(auto x: bridges){
        adj[x.first].push_back(x.second);
        adj[x.second].push_back(x.first);
    }
    //tour
    dfs(1,-1); //xdddddddddd
    vector<int>islands;
    int l = 1, r = N; int ans = 0;
    while(l <= r){
        int m = (l+r)/2;
        
        while(SZ(islands) < m) islands.push_back(node[SZ(islands) + 1]);
        while(SZ(islands) > m) islands.pop_back();
        
        if(query(islands) ==1){
            ans = node[m];
            r = m-1;
        }else{
            l = m+1;
        }
    }
    for(int i=1;i<=N;i++) adj[i].clear();
    return ans;
}

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