Submission #1164891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164891		KhoaDuy	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	9 ms	504 KiB

eastereggs

#include "grader.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=512;
int in[MAXN+1];
vector<vector<int>> graph(MAXN+1);
int tim=0;
void DFS(int u,int p){
    in[u]=tim;
    tim++;
    for(int v:graph[u]){
        if(v!=p){
            DFS(v,u);
        }
    }
}
int findEgg(int n,vector<pair<int,int>> bridges){
    tim=0;
    graph.clear(),graph.resize(n+1);
    for(int i=1;i<=n;i++){
        in[i]=0;
    }
    for(int i=0;i<bridges.size();i++){
        graph[bridges[i].first].push_back(bridges[i].second);
        graph[bridges[i].second].push_back(bridges[i].first);
    }
    DFS(1,-1);
    int low=0,high=tim-1;
    while(low<high){
        int mid=((high-low)>>1)+low;
        vector<int> v;
        for(int u=1;u<=n;u++){
            if(in[u]<=mid){
                v.push_back(u);
            }
        }
        if(query(v)){
            high=mid;
        }
        else{
            low=mid+1;
        }
    }
    for(int u=1;u<=n;u++){
        if(in[u]==low){
            return u;
        }
    }
}

Compilation message (stderr)

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
   49 | }
      | ^

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