Submission #613999

#	Time	Username	Problem	Language	Result	Execution time	Memory
613999		cheissmart	Highway Tolls (IOI18_highway)	C++14	100 / 100	321 ms	16408 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

void find_pair(int n, vi _u, vi _v, int a, int b) {
    V<vi> G(n), g(n);
    int m = SZ(_u);
    for(int i = 0; i < m; i++) {
        int u = _u[i], v = _v[i];
        G[u].PB(v);
        G[v].PB(u);
        g[u].PB(i);
        g[v].PB(i);
    }
    auto qry = [&] (vi s) -> ll {
        vi w(m);
        for(int i:s)
            w[i] = 1;
        return ask(w);
    };
    ll he = qry(vi());
    int lb = 0, rb = m - 1;
    while(lb <= rb) {
        int mb = (lb + rb) / 2;
        vi bad(mb + 1); iota(ALL(bad), 0);
        if(qry(bad) != he) rb = mb - 1;
        else lb = mb + 1;
    }

    auto BFS = [&] (int s) {
        vi d(n, -1);
        d[s] = 0;
        queue<int> q({s});
        while(q.size()) {
            int u = q.front(); q.pop();
            for(int v:G[u]) if(d[v] == -1) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
        return d;
    };

    int u = _u[lb], v = _v[lb];
    vi du = BFS(u), dv = BFS(v);

    vi s, t;
    for(int i = 0; i < n; i++) {
        if(du[i] < dv[i]) {
            s.PB(i);
        } else if(du[i] > dv[i]) {
            t.PB(i);
        }
    }

    sort(ALL(s), [&] (int i, int j) {
        return du[i] > du[j];
    });

    sort(ALL(t), [&] (int i, int j) {
        return dv[i] > dv[j];
    });

    lb = 0, rb = SZ(s) - 1;
    while(lb <= rb) {
        int mb = (lb + rb) / 2;
        vi bad;
        for(int i = 0; i <= mb; i++)
            for(int e:g[s[i]])
                bad.PB(e);

        if(qry(bad) != he) rb = mb - 1;
        else lb = mb + 1;
    }

    int S = s[lb];

    lb = 0, rb = SZ(t) - 1;
    while(lb <= rb) {
        int mb = (lb + rb) / 2;
        vi bad;
        for(int i = 0; i <= mb; i++)
            for(int e:g[t[i]])
                bad.PB(e);

        if(qry(bad) != he) rb = mb - 1;
        else lb = mb + 1;
    }

    int T = t[lb];

    answer(S, T);

}

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