oj.uz

Submission #67860

# Submission time Handle Problem Language Result Execution time Memory
67860 2018-08-15T11:26:04 Z quoriess Easter Eggs (info1cup17_eastereggs) C++14
81 / 100
 85 ms 616 KB 
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int MAXN=520;
vector<int> adj[MAXN];
vector<int> dizi;
void doldur(int node,int parent){
	dizi.push_back(node);
	for (auto it:adj[node])
	{
		if(it==parent)continue;
		doldur(it,node);
		dizi.push_back(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(low==high && sol==-1 ){
			sol=mid;
			break;
		}
		for (int i = 0; i <= mid; i++)
		{
			distinct.insert(dizi[i]);
		}
		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];
}

Subtask #1
32.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 248 KB Number of queries: 5
2 Incorrect 4 ms 308 KB Number of queries: 5
3 Incorrect 3 ms 512 KB Number of queries: 5
4 Incorrect 3 ms 616 KB Number of queries: 5

Subtask #2
34.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 616 KB Number of queries: 9
2 Incorrect 38 ms 616 KB Number of queries: 10
3 Incorrect 66 ms 616 KB Number of queries: 10
4 Incorrect 40 ms 616 KB Number of queries: 10

Subtask #3
15.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 616 KB Number of queries: 10
2 Incorrect 49 ms 616 KB Number of queries: 10
3 Incorrect 60 ms 616 KB Number of queries: 10
4 Incorrect 53 ms 616 KB Number of queries: 10