이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax=100005;
const int mmax=130005;
int n,m,i,p,u,ret;
long long mx,cate,A,B;
int unu[mmax],doi[mmax];
int in[nmax],bun[nmax];
int qu[2][nmax],d[2][nmax];
vector<int> v[nmax];
vector<int> q;
int dist(int x)
{
for(i=0;i<m;i++)
q[i]=1;
for(i=0;i<x;i++)
q[i]=0;
return ask(q);
}
void bfs(int x,int wh)
{
int nod;
u=1;
qu[wh][u]=x;d[wh][x]=1;
for(p=1;p<=u;p++)
{
x=qu[wh][p];
for(i=0;i<v[x].size();i++)
{
nod=v[x][i];
if(!d[wh][nod])
{
d[wh][nod]=d[wh][x]+1;
qu[wh][++u]=nod;
}
}
}
}
int cb(vector<int> mult)
{
int ans=0;
for(i=0;i<n;i++)
in[i]=0;
for(i=0;i<mult.size();i++)
in[mult[i]]=1;
for(int p=17;p>=0;p--)
if(ans+(1<<p)<=mult.size())
{
ans+=(1<<p);
for(i=0;i<m;i++)
if(in[unu[i]]==0&&in[doi[i]]==0) q[i]=0;
else q[i]=1;
q[ret]=0;
for(i=0;i<n;i++)
bun[i]=0;
for(i=0;i<ans;i++)
bun[mult[i]]=1;
for(i=0;i<m;i++)
if(bun[unu[i]]&&bun[doi[i]])
q[i]=0;
int cat=ask(q);
if(cat==1LL*cate*A) ans-=(1<<p);
}
return mult[ans];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int Aa, int Bb) {
n=N;m = U.size();
q.resize(m);
A=Aa;B=Bb;
for(i=0;i<m;i++)
{
v[U[i]].push_back(V[i]);
v[V[i]].push_back(U[i]);
unu[i]=U[i];doi[i]=V[i];
}
for(i=0;i<m;i++)
q[i]=1;
mx=ask(q);
cate=mx/B;
int ret=0;
for(int p=17;p>=0;p--)
if(ret+(1<<p)<=m&&dist(ret+(1<<p))==mx)
ret+=(1<<p);
int a=U[ret],b=V[ret];
bfs(a,0);bfs(b,1);
vector<int> multA,multB;
for(i=1;i<=n;i++)
{
int nod=qu[0][i];
if(d[0][nod]<d[1][nod]) multA.push_back(nod);
nod=qu[1][i];
if(d[1][nod]<d[0][nod]) multB.push_back(nod);
}
int x=cb(multA),y=cb(multB);
answer(x,y);
}
컴파일 시 표준 에러 (stderr) 메시지
highway.cpp: In function 'void bfs(int, int)':
highway.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
highway.cpp: In function 'int cb(std::vector<int>)':
highway.cpp:45:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<mult.size();i++)
~^~~~~~~~~~~~
highway.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ans+(1<<p)<=mult.size())
~~~~~~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |