oj.uz

답안 #67870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67870 2018-08-15T11:33:13 Z quoriess Easter Eggs (info1cup17_eastereggs) C++14
87 / 100
 62 ms 656 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;
		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
32.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 248 KB Number of queries: 5
2 Incorrect 5 ms 308 KB Number of queries: 5
3 Incorrect 4 ms 344 KB Number of queries: 5
4 Incorrect 3 ms 344 KB Number of queries: 5

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 528 KB Number of queries: 9
2 Correct 39 ms 528 KB Number of queries: 9
3 Correct 62 ms 628 KB Number of queries: 9
4 Correct 52 ms 628 KB Number of queries: 9

Subtask #3
15.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 656 KB Number of queries: 10
2 Correct 47 ms 656 KB Number of queries: 9
3 Incorrect 56 ms 656 KB Number of queries: 10
4 Incorrect 40 ms 656 KB Number of queries: 10