oj.uz

Submission #589617

# Submission time Handle Problem Language Result Execution time Memory
589617 2022-07-04T23:30:23 Z shezitt Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 20 ms 764 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int N = 520;
int n;
vector<int> g[N];
vector<int> a;
bool vis[N];

void dfs(int i){
	a.push_back(i);
	vis[i] = 1;
	for(auto x : g[i]){
		if(!vis[x]){
			dfs(x);
		}
	}
}

int findEgg (int nn, vector < pair < int, int > > bridges)
{
	memset(vis, 0, sizeof vis);
	n = nn;
	for(auto b : bridges){
		g[b.first].push_back(b.second);
		g[b.second].push_back(b.first);
	}
	dfs(1);
	int l = 0, r = n-2, ans = a[n-1];
	while(l <= r){
		int mid = (l+r)/2;
		vector<int> aux;
		for(int j=0; j<=mid; ++j){
			aux.push_back(a[j]);
		}
		if(query(aux)){
			ans = a[mid];
			r = mid-1;
		} else {
			l = mid+1;
		}
	}
	return ans;
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 408 KB Number of queries: 8
2 Correct 14 ms 520 KB Number of queries: 9
3 Correct 20 ms 752 KB Number of queries: 9
4 Correct 18 ms 712 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 700 KB Number of queries: 9
2 Correct 14 ms 660 KB Number of queries: 9
3 Correct 16 ms 764 KB Number of queries: 9
4 Correct 15 ms 752 KB Number of queries: 9