Submission #289541

#	Time	Username	Problem	Language	Result	Execution time	Memory
289541		infinite_iq	Highway Tolls (IOI18_highway)	C++14	51 / 100	251 ms	18376 KiB

highway

#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] ;
pi e [100009] ;
ll query ( vi ret ) {
        vi xxx ( n - 1 , 0 ) ;
        for ( auto u : ret ) {
                xxx [u] = 1 ;
        }
        return ask ( xxx ) ;
}
//
void fill ( int node , int p , int crnt , int st , int val ) {
        lev [node] = crnt ;
        if ( st == node ) val = 1 ;
        for ( auto u : v [node] ) {
                if ( u .fi == p ) C ;
                if ( val ) {
                        no .pb ( u.se ) ;
                }
                fill ( u .fi , node , crnt + 1 , st , val ) ;
        }
}
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 , int need ) {
        if ( ! need ) return node ;
        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 , 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 } ) ;
                e [i] = { a , b } ;
        }
        len = query ( no ) / A ;
        int l = -1 , r = n -2 ;
        while ( r - l > 1 ) {
                vi ret ;
                for ( int i = mid + 1 ; i <= r ; i ++ ) {
                        ret .pb ( i ) ;
                }
                ll cost = query ( ret ) ;
                if ( cost == len * X ) {
                        r = mid ;
                }
                else l = mid ;
        }
        fill ( 0 , 0 , 0 , 0 , 0 ) ;
        for ( int i = 0 ; i < n - 1 ; i ++ ) {
                if ( lev [e[i].fi] > lev [e[i].se] ) {
                        swap ( e [i].fi , e [i] .se ) ;
                }
        }
        no.clear () ;
        fill ( 0 , 0 , 0 , e [r].se , 0 ) ;
        ll crnt = query ( no ) ;
        for ( ll i = 1 ; i <= len ; i ++ ) {
                if ( i * A + ( len - i ) * B == crnt ) {
                        answer ( solve ( e [r].se , e [r] .fi , len - i ) , solve ( e [r] .fi , e [r] .se , i - 1 ) ) ;
                }
        }
}

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