Submission #98486

#	Time	Username	Problem	Language	Result	Execution time	Memory
98486		TAMREF	Easter Eggs (info1cup17_eastereggs)	C++11	100 / 100	32 ms	384 KiB

eastereggs

#include <bits/stdc++.h>
#define va first
#define vb second
#include "grader.h"

using namespace std;
using pii = pair<int,int>;
vector<int> G[550];
vector<int> ord;

void dfs(int x, int p){
    ord.push_back(x);
    for(int u : G[x]){
        if(u == p) continue;
        dfs(u, x);
    }
}

bool ini = true;
int findEgg (int N, vector<pii> bridges){
    if(ini){
        for(int i = 0; i < N-1; i++){
            G[bridges[i].va].push_back(bridges[i].vb);
            G[bridges[i].vb].push_back(bridges[i].va);
        }
        dfs(1,0);
        ini = false;
    }
    int s = 0, e = N - 1, m;
    while(s < e){
        m = (s+e) >> 1;
        int qry = query(vector<int>(ord.begin(), ord.begin() + m + 1));
        //printf("bs on [%d,%d], qry = %d\n",s,e,qry);
        if(qry) e = m;
        else s = m + 1;
    }
    //printf("m = %d\n",m);
    //for(int u : ord) printf("%d ",u); puts("");
    return ord[e];
}

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