Submission #466084

#	Time	Username	Problem	Language	Result	Execution time	Memory
466084		Pietra	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	21 ms	356 KiB

eastereggs

// temos uma árvore 
// perguntamos um set conexo e teremos como resposta se o ovo está lá
// queremos saber com menor qtd possivel de queries onde ele está 
// lineariza e procura qual o maior prefixo que n temos nd 
// a resp vai ser linear[ini]

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

vector<int> grafo[530], linear ; 

void dfs(int v, int p){
	
	linear.push_back(v) ; 

	for(auto a : grafo[v]) if(a != p) dfs(a, v) ; 

}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    for(int i = 1 ; i <= N ; i++) grafo[i].clear() ; 
    linear.clear() ; 

    for(auto a : bridges){
    	int u = a.first, v = a.second ; 
    	grafo[u].push_back(v), grafo[v].push_back(u) ; 
    }

    dfs(1, 0) ; 

    int ini = 0, fim = N - 1, mid ; 

    while(ini < fim){
    	mid = (ini + fim + 1) >> 1 ;
    	vector<int> tryy ; 
    	for(int i = 0 ; i < mid ; i++) tryy.push_back(linear[i]) ;  
    	if(query(tryy)) fim = mid - 1 ; // eu to no intervalo ent preciso pegar fim - 1 
        else ini = mid ; //n to mas eu sou o 1o q n ta? 
    }

    return linear[ini] ; 
    
}

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