oj.uz

Submission #466084

# Submission time Handle Problem Language Result Execution time Memory
466084 2021-08-17T21:45:55 Z Pietra Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 21 ms 356 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)
{
    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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Number of queries: 4
2 Correct 1 ms 200 KB Number of queries: 4
3 Correct 1 ms 200 KB Number of queries: 4
4 Correct 1 ms 200 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 328 KB Number of queries: 8
2 Correct 12 ms 328 KB Number of queries: 9
3 Correct 20 ms 348 KB Number of queries: 9
4 Correct 17 ms 340 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 356 KB Number of queries: 9
2 Correct 16 ms 328 KB Number of queries: 9
3 Correct 19 ms 328 KB Number of queries: 9
4 Correct 19 ms 356 KB Number of queries: 9