Submission #970501

#	Time	Username	Problem	Language	Result	Execution time	Memory
970501		jamesbamber	Highway Tolls (IOI18_highway)	C++17	51 / 100	140 ms	11972 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int M = U.size();
    vector<vector<pair<int,int>>> ad(N);
    for(int i=0; i<M; i++){
        ad[U[i]].push_back({V[i], i});
        ad[V[i]].push_back({U[i], i});
    }

    vector<int> up(N, -1), d(N);
    vector<int> order;
    auto bfs = [&](int s){
        vector<int> vis(N);
        queue<int> q; q.push(s);
        up.assign(N, -1), d.assign(N, 0);
        order.clear();
        vis[s] = 1;
        while(q.size()){
            int v = q.front(); q.pop();
            order.push_back(v);
            for(auto [u, id]: ad[v]){
                if(vis[u]) continue;
                vis[u] = 1;
                d[u] = d[v]+1;
                up[u] = id;
                q.push(u);
            }
        }
    };

    auto ask_depth = [&](int t){
        vector<int> w(M);
        for(int i=0; i<N; i++){
            if(d[i] <= t and up[i] != -1) w[up[i]] = 1;
        }
        return ask(w);
    };

    bfs(0);
    ll dist = ask_depth(0)/A;

    int l = 0, r = N;
    while(r-l > 1){
        int m = (l+r)/2;
        if(ask_depth(m) != dist*B) l = m;
        else r = m;
    }
    int mxdepth = r;


    auto ask_vec = [&](vector<pair<int,int>> &vec, int t){
        vector<int> w(M);
        for(int i=0; i<t; i++) 
            if(vec[i].second != -1) w[vec[i].second] = 1;
        return ask(w);
    };

    vector<pair<int,int>> susdepth;
    for(int i=0; i<N; i++){
        if(d[i] == mxdepth) susdepth.push_back({i, up[i]});
    }


    l = 0, r = susdepth.size();
    while(r-l > 1){
        int m = (l+r)/2;
        if(ask_vec(susdepth, m) == dist*A) l = m;
        else r = m;
    }
    int ans1 = susdepth[l].first;

    bfs(ans1);
    vector<pair<int,int>> ordersus;
    for(int x: order) ordersus.push_back({x, up[x]});

    l = 0, r = N;
    while(r-l > 1){
        int m = (l+r)/2;
        if(ask_vec(ordersus, m) != dist*B) l = m;
        else r = m;
    }
    int ans2 = ordersus[l].first;
    answer(ans1, ans2);
}

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