Submission #671528

#	Time	Username	Problem	Language	Result	Execution time	Memory
671528		Trunkty	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	20 ms	360 KiB

eastereggs

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll

#include "grader.h"

vector<int> roads[515];
int nextnode=1, val[515];

void dfs(int x, int p){
    val[nextnode] = x;
    nextnode++;
    for(int i:roads[x]){
        if(i!=p){
            dfs(i,x);
        }
    }
}

int findEgg(int n, vector<pair<int,int>> bridges){
    for(pair<int,int> i:bridges){
        roads[i.first].push_back(i.second);
        roads[i.second].push_back(i.first);
    }
    dfs(1,0);
    int low=1,high=n,mid;
    while(low!=high){
        mid = (low+high)/2;
        vector<int> x;
        for(int i=1;i<=mid;i++){
            x.push_back(val[i]);
        }
        if(query(x)){
            high = mid;
        }
        else{
            low = mid+1;
        }
    }
    int ans=val[low];
    nextnode = 1;
    for(int i=1;i<=n;i++){
        roads[i].clear();
        val[i] = 0;
    }
    return ans;
}

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