oj.uz

Submission #466083

# Submission time Handle Problem Language Result Execution time Memory
466083 2021-08-17T21:42:21 Z Pietra Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 3 ms 456 KB 
// 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)
{
    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, 1) ; 

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

    while(ini < fim){
    	mid = (ini + fim) >> 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
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 456 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 456 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 456 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -