Submission #601437

#	Time	Username	Problem	Language	Result	Execution time	Memory
601437		skittles1412	Highway Tolls (IOI18_highway)	C++17	51 / 100	186 ms	262144 KiB

highway

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

ll ask(const vector<int>& w);
void answer(int s, int t);

const int maxn = 1e5 + 5;

int n, m;
long qa, qb, def;
vector<pair<int, int>> graph[maxn];

int bsearch(const vector<int>& arr) {
    if (sz(arr) == 1) {
        return arr[0];
    }
    int mid = sz(arr) / 2;
    vector<int> l(arr.begin(), arr.begin() + mid),
        r(arr.begin() + mid, arr.end());
    vector<int> tmp(m);
    for (auto& a : l) {
        tmp[a] = true;
    }
    if (ask(tmp) > def) {
        return bsearch(l);
    } else {
        return bsearch(r);
    }
}

vector<array<int, 3>> cvals;

void dfs1(int u, int p = -1, int d = 0) {
    for (auto& [v, i] : graph[u]) {
        if (v != p) {
            cvals.push_back({i, v, d + 1});
            dfs1(v, u, d + 1);
        }
    }
}

int solve(int u) {
    cvals.clear();
    dfs1(u);
    vector<int> tmp(m);
    for (auto& a : cvals) {
        tmp[a[0]] = true;
    }
    long cx = ask(tmp);
    int depth = (cx - def) / (qb - qa);
    if (!depth) {
        return u;
    }
    tmp.clear();
    for (auto& [i, _, d] : cvals) {
        if (d == depth) {
            tmp.push_back(i);
        }
    }
    int cans = bsearch(tmp);
    for (auto& [i, v, _] : cvals) {
        if (i == cans) {
            return v;
        }
    }
    assert(false);
}

void find_pair(int _n, vector<int> us, vector<int> vs, int _qa, int _qb) {
    n = _n;
    m = sz(us);
    qa = _qa;
    qb = _qb;
    for (int i = 0; i < m; i++) {
        graph[us[i]].emplace_back(vs[i], i);
        graph[vs[i]].emplace_back(us[i], i);
    }
    def = ask(vector<int>(m));
    vector<int> tmp(m);
    iota(begin(tmp), end(tmp), 0);
    int ind = bsearch(tmp);
    auto erase = [&](int u) -> void {
        vector<pair<int, int>> tmp;
        for (auto& [v, a] : graph[u]) {
            if (a != ind) {
                tmp.emplace_back(v, a);
            }
        }
        swap(tmp, graph[u]);
    };
    erase(us[ind]);
    erase(vs[ind]);
    dbg(us[ind], vs[ind]);
    answer(solve(us[ind]), solve(vs[ind]));
}

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