oj.uz

Submission #969510

# Submission time Handle Problem Language Result Execution time Memory
969510 2024-04-25T09:04:36 Z tamir1 Easter Eggs (info1cup17_eastereggs) C++17
81 / 100
 14 ms 1028 KB 
#include <bits/stdc++.h>
#include "grader.h"
#define ff first
#define ss second
using namespace std;
vector<int> v[1009],u,m;
void dfs(int x,int p){
	u.push_back(x);
	for(int i:v[x]){
		if(i!=p) dfs(i,x);
	}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
	u={0};
    int i;
	for(i=1;i<=N;i++) v[i].clear();
    for(i=0;i<N-1;i++){
    	int x=bridges[i].ff;
    	int y=bridges[i].ss;
    	v[x].push_back(y);
    	v[y].push_back(x);
	}
	dfs(1,-1);
    int mid,l=1,r=N;
    while(r-l>1){
    	mid=(r+l+1)/2;
    	m.clear();
    	for(i=1;i<=mid;i++) m.push_back(u[i]);
    	if(query(m)) r=mid;
    	else l=mid;
	}
	if(query({u[r]})) return u[r];
	else return u[l];
}

Subtask #1
32.0 / 40.0

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

Subtask #2
34.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 740 KB Number of queries: 9
2 Partially correct 8 ms 1000 KB Number of queries: 10
3 Partially correct 12 ms 856 KB Number of queries: 10
4 Partially correct 10 ms 1008 KB Number of queries: 10

Subtask #3
15.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 1028 KB Number of queries: 10
2 Partially correct 14 ms 864 KB Number of queries: 10
3 Partially correct 11 ms 1012 KB Number of queries: 10
4 Partially correct 11 ms 760 KB Number of queries: 10