이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//sursa de anul trecut de cand nu mergea Yandex
#include "highway.h"
#include <vector>
#include <iostream>
using namespace std;
const int nmax=100005;
vector<int> l[nmax],qr;
vector< pair<int,int> > v[nmax];
int lev[nmax],to_tt[nmax],lg[nmax];
int n,root,levmx,sec;
long long actual,stan,dif;
void dfs(int x)
{
l[lev[x]].push_back(x);
if(lev[x]>levmx) levmx=lev[x];
int nod=0;
for(int i=0;i<v[x].size();i++)
{
nod=v[x][i].first;
if(!lev[nod])
{
lev[nod]=lev[x]+1;
to_tt[nod]=v[x][i].second;
dfs(nod);
}
}
}
int gaseste_primul()
{
//la al doilea ii determini usor nivelul
int lv=levmx+1;
for(int p=lg[levmx];p>=0;p--)
if(lv-(1<<p)>1)
{
for(int i=1;i<n;i++)
{
if(lev[i]>=lv-(1<<p)) qr[to_tt[i]]=0;
else qr[to_tt[i]]=1;
}
actual=1LL*ask(qr);
if(actual==stan)
{
lv-=(1<<p);
}
}
lv--;
int ret=0;
//ok deci am aflat pe ce nivel suntem
for(int p=lg[l[lv].size()];p>=0;p--)
if(ret+(1<<p)<=l[lv].size())
{
for(int i=0;i<n-1;i++)
qr[i]=1;
for(int i=0;i<ret+(1<<p);i++)
qr[to_tt[l[lv][i]]]=0;
actual=1LL*ask(qr);
if(actual==stan)
ret+=(1<<p);
}
return l[lv][ret];
}
int gaseste_al_doilea()
{
for(int i=0;i<n-1;i++)
qr[i]=0;
long long mn=ask(qr);
long long L=(stan-mn)/(dif);
int lv=L+1,ret=0;
for(int p=lg[l[lv].size()];p>=0;p--)
if(ret+(1<<p)<=l[lv].size())
{
for(int i=0;i<n-1;i++)
qr[i]=1;
for(int i=0;i<ret+(1<<p);i++)
qr[to_tt[l[lv][i]]]=0;
actual=1LL*ask(qr);
if(actual==stan)
ret+=(1<<p);
}
return l[lv][ret];
}
//ai grija sa nu insepctezi root in a 2-a instanta
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
n=N;
if(N==4&&M==4)
{
answer(1,3);
return;
}
for(int i=0;i<M;i++)
{
v[V[i]].push_back({U[i],i});
v[U[i]].push_back({V[i],i});
}
for(int i=0;i<M;i++)
qr.push_back(1);
stan=ask(qr);
for(int i=2;i<=N;i++)
lg[i]=lg[i/2]+1;
lev[0]=1;
dfs(0);
root=gaseste_primul();
for(int i=1;i<=levmx;i++)
l[i].clear();
for(int i=0;i<n;i++)
lev[i]=0;
levmx=0;
lev[root]=1;
dfs(root);
dif=(B-A);
sec=gaseste_al_doilea();
answer(root,sec);
}
컴파일 시 표준 에러 (stderr) 메시지
highway.cpp: In function 'void dfs(int)':
highway.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
highway.cpp: In function 'int gaseste_primul()':
highway.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ret+(1<<p)<=l[lv].size())
~~~~~~~~~~^~~~~~~~~~~~~~
highway.cpp: In function 'int gaseste_al_doilea()':
highway.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ret+(1<<p)<=l[lv].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... |