oj.uz

Submission #969512

# Submission time Handle Problem Language Result Execution time Memory
969512 2024-04-25T09:07:37 Z tamir1 Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 12 ms 1252 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){
    	mid=(r+l)/2;
    	m.clear();
    	for(i=1;i<=mid;i++) m.push_back(u[i]);
    	if(query(m)) r=mid;
    	else l=mid+1;
	}
	return u[r];
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 480 KB Number of queries: 8
2 Correct 8 ms 992 KB Number of queries: 9
3 Correct 11 ms 1252 KB Number of queries: 9
4 Correct 11 ms 1012 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 872 KB Number of queries: 9
2 Correct 9 ms 516 KB Number of queries: 9
3 Correct 12 ms 740 KB Number of queries: 9
4 Correct 10 ms 760 KB Number of queries: 9