oj.uz

Submission #522035

# Submission time Handle Problem Language Result Execution time Memory
522035 2022-02-03T15:52:38 Z iskhakkutbilim Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 19 ms 448 KB 
#include<bits/stdc++.h>
 #include "grader.h"

using namespace std;

vector<int> g[515];

vector<int> island;
void dfs(int v, int par){
	island.push_back(v);
	for(auto to : g[v]){
		if(to == par) continue;
			dfs(to, v);
		
	}
}


int findEgg (int N, vector < pair < int, int > > bridges)
{
	
	for(int i = 1;i <= N; i++){
		g[i].clear();
	}
	island.clear();
	for(int i = 0;i < N-1; i++){
		int a = bridges[i].first;
		int b = bridges[i].second;
		g[a].push_back(b);
		g[b].push_back(a);
	}
   	dfs(1, -1);
   	//cout << 't';
   	// for(auto x : qu){
		// cout << x << " ";
	// }
	// cout << "\n";
//    	
	int l = 0, r = island.size()-1;
	while(r > l){
		int m = (l + r) / 2;
		vector<int> st;
		for(int i = 0;i <= m; i++){
			st.push_back(island[i]);
		}
		if(query(st)){
			r = m;
		}else l = m + 1;
	}
   	return island[l];
}

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 5 ms 328 KB Number of queries: 8
2 Correct 12 ms 328 KB Number of queries: 9
3 Correct 14 ms 344 KB Number of queries: 9
4 Correct 19 ms 448 KB Number of queries: 9

Subtask #3
20.0 / 20.0

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