이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std ;
#define mid (l+r)/2
#define fi first
#define se second
#define pb push_back
#define C continue
#define mem(x,y) memset(x,y,sizeof(x))
typedef long long ll ;
typedef pair < int , int > pi ;
typedef vector < int > vi ;
typedef vector < pi > vpi ;
#include "highway.h"
ll n , X , Y , len ;
vi no ;
vpi v [100009] , ord ;
int lev [100009] ;
ll query ( vi ret ) {
vi xxx ( n - 1 , 0 ) ;
for ( auto u : ret ) {
xxx [u] = 1 ;
}
return ask ( xxx ) ;
}
bool cmp ( pi x , pi y ) {
return lev [x.fi] < lev [y.fi] ;
}
void dfs ( int node , int p , int crnt , int id ) {
lev [node] = crnt ;
if ( crnt ) {
ord .pb ( { node , id } ) ;
}
for ( auto u : v [node] ) {
if ( u.fi == p ) C ;
dfs ( u .fi , node , crnt + 1 , u.se ) ;
}
}
int solve ( int node , int p ) {
mem ( lev , 0 ) ;
ord .clear () ;
dfs ( node , p , 0 , - 1 ) ;
sort ( ord .begin () , ord .end () , cmp ) ;
int l = -1 , r = ord .size () - 1 ;
while ( r - l > 1 ) {
vi ret ;
for ( int i = mid + 1 ; i <= r ; i ++ ) {
ret .pb ( ord [i] .se ) ;
}
ll cost = query ( ret ) ;
if ( cost == len * X ) {
r = mid ;
}
else l = mid ;
}
return ord [r].fi ;
}
void find_pair ( int N, vi U, vi V, int A , int B ) {
n = N , len = query ( no ) / A , X = A , Y = B ;
for ( int i = 0 ; i < n - 1 ; i ++ ) {
int a = U [i] , b = V [i] ;
v [a] .pb ( { b , i } ) ;
v [b] .pb ( { a , i } ) ;
}
answer ( 0 , solve ( 0 , 0 ) ) ;
}
# | 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... |