제출 #1189801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189801		fluke	Easter Eggs (info1cup17_eastereggs)	C++20	32 / 100	5 ms	1084 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#define emb emplace_back
#define em emplace

using namespace std;

vector <int> adj[513];
vector <int> ask[513];
vector <int> temp;
vector <bool> vis(513);

void dfs(int node){
    temp.emb(node);
    ask[temp.size()] = temp;

    for(int next_node : adj[node]){
        if(vis[next_node])continue;
        vis[next_node] = true;
        dfs(next_node);
    }
}


int findEgg (int N, vector < pair < int, int > > bridges)
{

    for(auto [u,v] : bridges){
        adj[u].emb(v);
        adj[v].emb(u);
    }

    vis[1] = true;
    dfs(1);

    // for(int i=1;i<=N;i++){
    //     cout<<i<<" : " ;
    //     for(auto x : ask[i]){
    //         cout<<x<<" ";
    //     }
    //     cout<<"\n";
    // }

    int left = 1 , right = N;

    int ans = 1;
    while(left <= right){
        
        int mid = (left+ right)/2;

        if(query(ask[mid])){
            ans = ask[mid].back();
            right = mid - 1;
        }
        else left = mid + 1;
    }

    return ans;
} 

// int main(){
//     int n;
//     cin>>n;

//     vector <pair<int,int> > edge_list;
//     for(int i = 1 ; i<=n -1 ; i++){
//         int x,y;
//         cin>>x>>y;
//         edge_list.emb(x,y);
//     }

//     findEgg(n,edge_list);
// }

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