oj.uz

Submission #67874

# Submission time Handle Problem Language Result Execution time Memory
67874 2018-08-15T11:35:11 Z quoriess Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 74 ms 696 KB 
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int MAXN=520;
typedef pair<int,int> pii;
vector<int> adj[MAXN];
vector<pii> dizi;
void doldur(int node,int parent){
	dizi.push_back(pii(parent,node));
	for (auto it:adj[node])
	{
		if(it==parent)continue;
		doldur(it,node);
	}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
	dizi.clear();
	for(int i=1;i<=N;i++){
		adj[i].clear();
	}
	for(int i=0;i<(int)bridges.size();i++){
		adj[bridges[i].first].push_back(bridges[i].second);
		adj[bridges[i].second].push_back(bridges[i].first);
	}
	doldur(1,-1);
	//cout<<" dizisi\n";
	int low=0,high=dizi.size()-1;
	int mid=(low+high)/2;
	int sol=-1;
	while(low<=high){
		mid=(low+high)/2;
		//cout << "low: "<<low<<" high: "<<high<<" mid: "<<mid<<"\n";
		set<int> distinct;
		if(sol==-1 && low==high){sol=mid;break;}
		for (int i = 0; i <= mid; i++)
		{
			if(dizi[i].first!=-1)distinct.insert(dizi[i].first);
			distinct.insert(dizi[i].second);
		}
		vector<int> sorg;	
		
		for (auto s:distinct)
		{
			sorg.push_back(s);
			//cout << s<<" ";
		}
		//cout<<"\n";
		if(query(sorg)){
			high=mid-1;
			sol=mid;
		}
		else low=mid+1;
	}
	return dizi[sol].second;
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 600 KB Number of queries: 8
2 Correct 38 ms 600 KB Number of queries: 9
3 Correct 74 ms 600 KB Number of queries: 9
4 Correct 69 ms 696 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 696 KB Number of queries: 9
2 Correct 70 ms 696 KB Number of queries: 9
3 Correct 67 ms 696 KB Number of queries: 9
4 Correct 54 ms 696 KB Number of queries: 9