Submission #995454

#	Time	Username	Problem	Language	Result	Execution time	Memory
995454		Forested	Meetings (IOI18_meetings)	C++17	Compilation error	0 ms	0 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)size(x)
#define ALL(x) begin(x), end(x)
template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

#include "highway.h"

void find_pair(i32 n, V<i32> u, V<i32> v, i32 _a, i32 _b) {
    i64 a = _a, b = _b;
    i32 m = LEN(u);
    i64 d = ask(V<i32>(m, 0));
    i32 path = d / a;
    i32 ok = 0, ng = m;
    while (ng - ok > 1) {
        i32 mid = (ok + ng) / 2;
        V<i32> w(m, 0);
        fill(w.begin(), w.begin() + mid, 1);
        if (ask(w) == d) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    i32 ed = ok;
    VV<pair<i32, i32>> g(n);
    REP(i, ed + 1, m) {
        g[u[i]].emplace_back(v[i], i);
        g[v[i]].emplace_back(u[i], i);
    }
    i32 r0 = u[ed], r1 = v[ed];
    V<i32> dist(n, -1), from(n, -1);
    queue<i32> que;
    que.push(r0);
    que.push(r1);
    dist[r0] = 0;
    dist[r1] = 0;
    from[r0] = r0;
    from[r1] = r1;
    while (!que.empty()) {
        i32 v = que.front();
        que.pop();
        for (auto [u, e] : g[v]) {
            if (dist[u] == -1) {
                dist[u] = dist[v] + 1;
                from[u] = from[v];
                que.push(u);
            }
        }
    }
    V<pair<i32, i32>> ss, ts;
    REP(i, n) {
        if (from[i] != r0) {
            continue;
        }
        for (auto [j, e] : g[i]) {
            if (from[j] == r0 && dist[j] == dist[i] - 1) {
                ss.emplace_back(dist[i], e);
            }
        }
    }
    REP(i, n) {
        if (from[i] != r1) {
            continue;
        }
        for (auto [j, e] : g[i]) {
            if (from[j] == r1 && dist[j] == dist[i] - 1) {
                ts.emplace_back(dist[i], e);
            }
        }
    }
    sort(ALL(ss), greater());
    sort(ALL(ts), greater());
    i32 s = -1, t = -1;
    ok = 0;
    ng = LEN(ss) + 1;
    while (ng - ok > 1) {
        i32 mid = (ok + ng) / 2;
        V<i32> w(m, 0);
        fill(w.begin(), w.begin() + ed, 1);
        REP(i, mid) {
            w[ss[i].second] = 1;
        }
        if (ask(w) == d) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    if (ok == LEN(ss)) {
        s = r0;
    } else {
        i32 e = ss[ok].second;
        if (dist[u[e]] > dist[v[e]]) {
            s = u[e];
        } else {
            s = v[e];
        }
    }
    ok = 0;
    ng = LEN(ts) + 1;
    while (ng - ok > 1) {
        i32 mid = (ok + ng) / 2;
        V<i32> w(m, 0);
        fill(w.begin(), w.begin() + ed, 1);
        REP(i, mid) {
            w[ts[i].second] = 1;
        }
        if (ask(w) == d) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    if (ok == LEN(ts)) {
        t = r1;
    } else {
        i32 e = ts[ok].second;
        if (dist[u[e]] > dist[v[e]]) {
            t = u[e];
        } else {
            t = v[e];
        }
    }
    answer(s, t);
}

Compilation message (stderr)

meetings.cpp:35:10: fatal error: highway.h: No such file or directory
   35 | #include "highway.h"
      |          ^~~~~~~~~~~
compilation terminated.