oj.uz

Submission #797786

# Submission time Handle Problem Language Result Execution time Memory
797786 2023-07-29T22:26:17 Z MODDI Easter Eggs (info1cup17_eastereggs) C++14
66 / 100
 39 ms 464 KB 
#//include "grader.cpp"
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
int n;
vi G[550], euler;
void dfs(int at, int p){
	euler.pb(at);
	for(auto next : G[at]){
		if(next == p)	continue;
		dfs(next, at);
		euler.pb(at);
	}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
    n = N;
    for(int i = 0; i < n; i++)	G[i].clear();
    for(auto t : bridges){
		G[t.first].pb(t.second);
		G[t.second].pb(t.first);
	}
	euler.clear();
	dfs(1, 0);
	int l = 0, r = (int)euler.size()-1, ans = -1;
	while(r-l>=1){
		int mid = (l + r) / 2;
		set<int> ask;
		for(int i = l; i <= mid; i++){
			ask.insert(euler[i]);
		}
		vi is;
		for(auto t : ask)	is.pb(t);
		int s = query(is);
		if(s == 1){
			ans = mid;
			r = mid;
		}
		else{
			l = mid+1;
		}
	}
	return euler[ans];
}

Subtask #1
26.4 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 208 KB Number of queries: 7
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
26.4 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 12 ms 336 KB Number of queries: 13
2 Partially correct 6 ms 344 KB Number of queries: 10
3 Partially correct 12 ms 372 KB Number of queries: 11
4 Partially correct 10 ms 336 KB Number of queries: 10

Subtask #3
13.2 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 39 ms 464 KB Number of queries: 15
2 Partially correct 10 ms 336 KB Number of queries: 10
3 Partially correct 13 ms 372 KB Number of queries: 12
4 Partially correct 8 ms 336 KB Number of queries: 10