제출 #775424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
775424		Alihan_8	통행료 (IOI18_highway)	C++17	51 / 100	122 ms	16736 KiB

highway

#include <bits/stdc++.h>

#include "highway.h"

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
//#define int long long

template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}

template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag = false;
    if ( x < y ){
        x = y; flag |= true;
    }
    return flag;
}


void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
    int m = (int)U.size();
    assert(m == n - 1);
    vector <pair<int,int>> g[n], edge(m);
    vector <int> tree;
    for ( int i = 0; i < m; i++ ){
        g[U[i]].pb({V[i], i});
        g[V[i]].pb({U[i], i});
    }
    function <void(int,int)> dfs = [&](int x, int par){
        for ( auto [to, id]: g[x] ){
            if ( to == par ){
                continue;
            } tree.pb(id);
            edge[id] = {x, to};
            dfs(to, x);
        }
    };
    auto dis = ask(vector <int> (m, 0)) / A * B;
    auto get = [&](int root){
        tree.clear();
        dfs(root, -1);
        int l = 0, r = m - 1;
        while ( l < r ){
            int md = (l + r) >> 1;
            vector <int> f(m, 0);
            for ( int i = 0; i <= md; i++ ){
                f[tree[i]] = 1;
            }
            if ( ask(f) == dis ) r = md;
            else l = md + 1;
        }
        return edge[tree[l]].second;
    };
    int s = get(0), t = get(s);
    answer(s, t);
}

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