# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
288159 | infinite_iq | Highway Tolls (IOI18_highway) | C++14 | 0 ms | 0 KiB |
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>
using namespace std ;
#define mid (l+r)/2
#define pb push_back
#define fi first
#define se second
#define C continue
typedef long long ll ;
typedef pair < int , int > pi ;
typedef vector < int > vi ;
typedef vector < ll > vll ;
typedef vector < pi > vpi ;
#include "highway.h"
ll n , m , len , XXX , num ;
vpi v [100009] ;
vi no ;
ll query ( vi ret ) {
num ++ ;
if ( nun > 60 ) {
cout << 5 / 0 << endl ;
}
vi v ( m , 0 ) ;
for ( auto u : ret ) v [u] = 1 ;
return ask (v) ;
}
void dfs ( int node , int p , int lev ) {
if ( lev == len ) {
answer ( 0 , node ) ;
return ;
}
vpi ret ;
for ( auto u : v [node] ) {
if ( u .fi == p ) C ;
ret .pb ( u ) ;
}
int l = -1 , r = ret .size () - 1 ;
while ( r - l > 1 ) {
vi crnt ;
for ( int i = mid + 1 ; i <= r ; i ++ ) {
crnt .pb ( ret [i] .se ) ;
}
int cost = query ( crnt ) ;
if ( cost == len * XXX ) {
r = mid ;
}
else {
l = mid ;
}
}
dfs ( ret [r].fi , node , lev + 1 ) ;
}
void find_pair ( int N , vi U, vi V , int A , int B ) {
n = N , m = U .size () , len = query ( no ) / A , XXX = A ;
for ( int i = 0 ; i < m ; i ++ ) {
int a = U [i] , b = V [i] ;
v [a] .pb ( { b , i } ) ;
v [b] .pb ( { a , i } ) ;
}
dfs ( 0 , 0 , 0 ) ;
}