제출 #289479

#제출 시각아이디문제언어결과실행 시간메모리
289479infinite_iq통행료 (IOI18_highway)C++14
5 / 100
193 ms10896 KiB
#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 typedef pair < int , int > pi ; typedef vector < int > vi ; typedef vector < pi > vpi ; #include "highway.h" int n , X , Y , len ; vi no ; vpi v [100009] , ord ; int lev [100009] ; int 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 ) ; } } void find_pair ( int N, vi U, vi V, int A , int B ) { n = N , len = query ( no ) / A ; 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 } ) ; } dfs ( 0 , 0 , 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 ) ; } int cost = query ( ret ) ; if ( cost == len * A ) { r = mid ; } else l = mid ; } answer ( 0 , ord [r] .fi ) ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...