이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "highway.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll m,i,x[202020],y[202020],jarak,p[202020],te,o[202020];
vector<ll> v[202020],w[202020];
vector<int> z,q1,q2;
void dfs(ll aa,ll bb,ll cc)
{
p[aa]=bb;
//dep[aa]=cc;
ll ii;
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=bb)
{
x[++te]=w[aa][ii];
y[te]=v[aa][ii];
o[w[aa][ii]]=v[aa][ii];
dfs(v[aa][ii],aa,cc+1);
}
}
void dfs1(ll aa)
{
ll ii;
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=p[aa])
{
// cout<<w[aa][ii]<<"_\n";
z[w[aa][ii]]=0;
dfs1(v[aa][ii]);
}
}
void dfs2(ll aa,ll bb)
{
ll ii;
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=p[aa])
{
if(bb==1)
{
q1.pb(w[aa][ii]);
}
dfs2(v[aa][ii],bb-1);
}
}
void dfs3(ll aa,ll bb,ll cc)
{
ll ii;
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=p[aa]&&v[aa][ii]!=cc)
{
if(bb==1)
q2.pb(w[aa][ii]);
dfs3(v[aa][ii],bb-1,cc);
}
}
void ubah(ll aa,ll bb,ll cc)
{
ll ii;
for(ii=aa;ii<=bb;ii++)
z[x[ii]]=cc;
}
void ubah1(ll aa,ll bb,ll cc)
{
ll ii;
for(ii=aa;ii<=bb;ii++)
z[q1[ii]]=cc;
}
void ubah2(ll aa,ll bb,ll cc)
{
ll ii;
for(ii=aa;ii<=bb;ii++)
z[q2[ii]]=cc;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
m = U.size();
for(i=0;i<m;i++)
{
v[U[i]].pb(V[i]);
w[U[i]].pb(i);
v[V[i]].pb(U[i]);
w[V[i]].pb(i);
}
dfs(0,0,0);
ll L=0,R=m-1,C,H;
for(i=0;i<m;i++)
z.pb(0);
ll tem=ask(z);
jarak=tem/A;
ask(z);
while(L<=R)
{
C=(L+R)/2;
ubah(1,C,1);
ubah(C+1,m,0);
if(ask(z)==tem)
{
H=C+1;
L=C+1;
}
else
R=C-1;
}
ubah(1,m,1);
z[x[H]]=0;
dfs1(y[H]);
ll tom=ask(z);
//for(i=0;i<m;i++)
// cout<<i<<" "<<z[i]<<"\n";
//cout<<y [H]<<" "<<H<<" "<<tom<<" "<<tem<<"\n";
if(tom==tem)
{
if(jarak==1)
{
answer(y[H],p[y[H]]);
}
else
{
dfs2(y[H],jarak-1);
L=0;
R=q1.size()-1;
ll H1;
while(L<=R)
{
C=(L+R)/2;
ubah1(0,C,0);
ubah1(C+1,q1.size()-1,1);
if(ask(z)==tem)
{
H1=C;
R=C-1;
}
else
L=C+1;
}
answer(o[q1[H1]],p[y[H]]);
}
//cout<<"A";
}
else
{
ll jer=jarak-((tom-tem)/(B-A)),H1,H2;
if(jer==1)
H1=y[H];
else
{
dfs2(y[H],jer-1);
//cout<<jer<<"\n";
L=0;
R=q1.size()-1;
ubah(1,m,0);
//for(i=0;i<q1.size();i++)
// cout<<q1[i]<<"*\n";
while(L<=R)
{
C=(L+R)/2;
ubah1(0,C,0);
ubah1(C+1,q1.size()-1,1);
if(ask(z)==tem)
{
// cout<<C<<"_()\n";
H1=o[q1[C]];
R=C-1;
}
else
L=C+1;
}
// cout<<H1<<"\n";
}
ubah(1,m,0);
dfs3(p[y[H]],jarak-jer,y[H]);
L=0;
R=q2.size()-1;
//for(i=0;i<q2.size();i++)
// cout<<q2[i]<<"_\n";
while(L<=R)
{
C=(L+R)/2;
ubah2(0,C,0);
ubah2(C+1,q2.size()-1,1);
if(ask(z)==tem)
{
H2=o[q2[C]];
R=C-1;
}
else
L=C+1;
}
//cout<<H1<<" "<<H2<<"\n";
answer(H1, H2);
}
}
컴파일 시 표준 에러 (stderr) 메시지
highway.cpp: In function 'void dfs(ll, ll, ll)':
highway.cpp:17:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
highway.cpp: In function 'void dfs1(ll)':
highway.cpp:29:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
highway.cpp: In function 'void dfs2(ll, ll)':
highway.cpp:40:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
highway.cpp: In function 'void dfs3(ll, ll, ll)':
highway.cpp:53:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:195:9: warning: 'H2' may be used uninitialized in this function [-Wmaybe-uninitialized]
answer(H1, H2);
~~~~~~^~~~~~~~
highway.cpp:195:9: warning: 'H1' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:141:18: warning: 'H1' may be used uninitialized in this function [-Wmaybe-uninitialized]
answer(o[q1[H1]],p[y[H]]);
^
highway.cpp:111:6: warning: 'H' may be used uninitialized in this function [-Wmaybe-uninitialized]
dfs1(y[H]);
~~~~^~~~~~
# | 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... |