Submission #288192

#	Time	Username	Problem	Language	Result	Execution time	Memory
288192		infinite_iq	Highway Tolls (IOI18_highway)	C++14	12 / 100	255 ms	262148 KiB

highway

#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 ;
vpi v [100009] ;
vi no ;
ll yes [100009] ;
ll query ( vi ret ) {
        vi v ( m , 0 ) ;
        for ( auto u : ret ) v [u] = 1 ;
        return ask (v) ;
}
void fill ( int node , int p , int lev ) {
        yes [node] = ( lev == len ) ;
        for ( auto u : v [node] ) {
                if ( u .fi == p ) C ;
                fill ( u .fi , node , lev + 1 ) ;
                yes [node] = max ( yes [node] , yes [u.fi] ) ;
        }
}
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 ;
                if ( !yes [u.fi] ) 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 ) ;
                }
                ll 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 } ) ;
        }
        fill ( 0 , 0 , 0 ) ;
        dfs  ( 0 , 0 , 0 ) ;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31