This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
///~~~LOTA~~~///
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define append push_back
#define add insert
#define nl '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define terminator main
#define N 90000
int d;
int ve[N];
int par[N];
int dept[N];
vector<pii> e[N];
vector<int> x[N];
void dfs(int v,int u){
d=max(d,dept[v]);
x[dept[v]].append(v);
for(auto& i:e[v]){
if(i.ff==u)
continue;
dept[i.ff]=dept[v]+1;
ve[i.ff]=i.ss;
par[i.ff]=v;
dfs(i.ff,v);
}
}
void find_pair(int n,vector<int> v,vector<int> u,int a,int b){
ll m,o,p,q,r,s,t;
vector<int> h;
for(int i=1;i<n;i++)
h.append(0);
for(int i=m=d=0;i<n-1;i++){
e[v[i]].append({u[i],i});
e[u[i]].append({v[i],i});
}
o=ask(h);
m=(o/a)*b;
dfs(0,-1);
q=d;
for(int i=65536;i>0;i/=2){
if(i>=q) continue;
for(int j=1;j<=q-i;j++)
for(auto& k:x[j])
h[ve[k]]=1;
r=ask(h);
for(int j=1;j<=q-i;j++)
for(auto& k:x[j])
h[ve[k]]=0;
if(r==m) q-=i;
}
p=q;
for(int i=65536;i>0;i/=2){
if(i>p) continue;
for(auto& j:x[p-i+1])
h[ve[j]]=1;
r=ask(h);
for(auto& j:x[p-i+1])
h[ve[j]]=0;
if(r-o==b-a) p-=i;
}
s=t=0;
for(int i=65536;i>0;i/=2){
if(s+i>x[q].size())
continue;
for(int j=0;j<s+i;j++)
h[ve[x[q][j]]]=1;
r=ask(h);
for(int j=0;j<s+i;j++)
h[ve[x[q][j]]]=0;
if(r==o) s+=i;
}
s=q=x[q][s];
while(dept[q]>p)
q=par[q];
for(int i=65536;i>0;i/=2){
if(t+i>x[p].size())
continue;
for(int j=0;j<t+i;j++)
h[ve[x[p][j]]]=1;
h[ve[q]]=0;
r=ask(h);
for(int j=0;j<t+i;j++)
h[ve[x[p][j]]]=0;
if(r==o) t+=i;
}
if(t==x[p].size()) t=q;
else t=x[p][t];
answer(s,t);
}
Compilation message (stderr)
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:72:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if(s+i>x[q].size())
| ~~~^~~~~~~~~~~~
highway.cpp:85:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | if(t+i>x[p].size())
| ~~~^~~~~~~~~~~~
highway.cpp:95:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | if(t==x[p].size()) t=q;
| ~^~~~~~~~~~~~~
# | 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... |