제출 #1315823

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

eastereggs

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

using namespace std;

const int mxN = 512 + 10;

vector<int> adj[mxN];
vector<int> lt;

void reset(int n){
    lt.clear();
    for(int i = 1; i <= n; ++i) adj[i].clear();
}

void dfs(int u = 1, int par = 0){
    lt.push_back(u);
    for(auto it : adj[u]){
        if(it ^ par){
            dfs(it, u);
        }
    }
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    reset(N);
    for(auto [u, v] : bridges){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs();
    int st = 0, en = N - 1, ans = 0;
    while(st <= en){
        int mid = (st + en) / 2;
        vector<int> ltc;
        for(int j = 0; j <= mid; ++j) ltc.push_back(lt[j]);
        if(query(ltc)) ans = ltc.back(), en = mid - 1;
        else st = mid + 1;
    }
    return ans;
}

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