Submission #1189836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189836		yoruonivamp	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	508 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;

void dfs(int u, int prev, vector<int> &order, vector<vector<int>> &adj){
    order.emplace_back(u);
    for(auto v: adj[u]){
        if(v!=prev) dfs(v,u,order,adj);
    }
}

int findEgg(int N, vector<pair<int,int>> bridges){
    vector<int> order;
    vector<vector<int>> adj(N+1);
    for(auto [u,v]: bridges){
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }dfs(1,-1,order,adj);
    int l = 0, r = N-1;
    while(l<r){
        vector<int> tmp;
        int mid = (l+r)/2;
        for(int i = 0; i <= mid; i++) tmp.emplace_back(order[i]);
        if(query(tmp)) r=mid;
        else l=mid+1;
    }return order[l];
}

// vector<pair<int,int>> b = {{1,2},{1,3},{2,4},{2,5}};
// int n = 5;

// int main(){
//     cout << findEgg(n,b);
// }

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