제출 #288157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288157		infinite_iq	통행료 (IOI18_highway)	C++14	5 / 100	141 ms	7832 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 query ( vi ret ) {
        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 ) ;
}

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