This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "highway.h"
#define pb push_back
#define fi first
#define se second
using namespace std;
long long a,b,n;const int N=90090;
int pa[N];long long l;vector<int>vv;vector<pair<int,int>>v[N];
vector<int>w;
void dfs(int x,int p,long long le)
{
pa[x]=p;
if(le==0){
vv.pb(x);return;
}
for(auto it:v[x])
{
if(it.se==p)continue;
dfs(it.fi,it.se,le-1);
}
}
int ch(int ll,int r)
{
w.clear();
for(int i=0;i<n-1;i++)w.pb(0);
for(int i=ll;i<=r;i++)
{
w[pa[vv[i]]]=1;
}
long long x=ask(w);
w.clear();
long long y=a*l;
if(x>y)return 1;
return 0;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
a=A;b=B;
w.clear();
n=N;
for(int i=0;i<n-1;i++)w.pb(0);
l=ask(w)/a;
for(int i=0;i<n-1;i++)
{
v[V[i]].pb({U[i],i});
v[U[i]].pb({V[i],i});
}
dfs(0,-1,l);
int m=vv.size();
int st=0,end=m-1;
while(st<end)
{
int mid=st+end;mid/=2;
if(ch(st,mid)) end=mid;
else st=mid+1;
}
answer(0,vv[st]);
}
/*
4 3
1 2
0 3
0 1
1 2
1 3
*/
# | 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... |