oj.uz

Submission #589615

# Submission time Handle Problem Language Result Execution time Memory
589615 2022-07-04T23:23:32 Z shezitt Easter Eggs (info1cup17_eastereggs) C++14
87 / 100
 24 ms 752 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-1, ans = -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
32.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 208 KB Number of queries: 5
2 Partially correct 1 ms 208 KB Number of queries: 5
3 Partially correct 1 ms 208 KB Number of queries: 5
4 Partially correct 1 ms 208 KB Number of queries: 5

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 404 KB Number of queries: 9
2 Correct 13 ms 620 KB Number of queries: 9
3 Correct 24 ms 720 KB Number of queries: 9
4 Correct 14 ms 700 KB Number of queries: 9

Subtask #3
15.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 18 ms 752 KB Number of queries: 10
2 Correct 17 ms 656 KB Number of queries: 9
3 Partially correct 16 ms 736 KB Number of queries: 10
4 Partially correct 19 ms 700 KB Number of queries: 10