이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int>ve;
vector<pair<int,int>>l;
bool ok[520];
void constructie(int poz,int n)
{
int nr=0;
while(++nr<n)
{
ok[poz]=true;
ve.push_back(poz);
if(ok[l[poz].first]==true)
poz=l[poz].second;
else
poz=l[poz].first;
}
ve.push_back(poz);
return;
}
//int query(vector < int > islands);
int findEgg(int N, vector < pair < int, int > > bridges)
{
ve.clear();
l.clear();
int nra[520]={0};
l.resize(N+5);
ve.resize(N+5);
for(int i=1;i<=N;++i)
ok[i]=false;
for(auto x:bridges)
{
++nra[x.first];
++nra[x.second];
if(nra[x.first]==1)
l[x.first].first=x.second;
else
l[x.first].second=x.second;
if(nra[x.second]==1)
l[x.second].first=x.first;
else
l[x.second].second=x.first;
}
for(int i=1;i<=N;++i)
{
if(nra[i]==0)
{
constructie(i,N);
break;
}
}
int b=0,e=N-1;
while(b<=e)
{
int m=(b+e)/2;
vector<int>q;
for(int x=b;x<=e;++x)
q.push_back(ve[x]);
if(query(q))
e=m-1;
else
b=m+1;
q.clear();
}
return ve[b];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |