Submission #415457

#	Time	Username	Problem	Language	Result	Execution time	Memory
415457		2qbingxuan	Highway Tolls (IOI18_highway)	C++14	7 / 100	365 ms	12016 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(x...) qqbx(#x, x)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\e[1;32m(" << s << ") = ("), ... , (std::cerr << a << (--cnt ? ", " : "\e[0m)\n")));
}
#define pary(x...) danb(#x, x)
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        std::cerr << (f++ ? ", " : "") << *L;
    std::cerr << " ]\e[0m\n";
}
#else
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;
using ll = long long;
const int maxn = 100025;
vector<pair<int,int>> g[maxn];
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int M = U.size();
    for (int i = 0; i < M; i++) {
        g[U[i]].emplace_back(V[i], i);
        g[V[i]].emplace_back(U[i], i);
    }

    auto bfs = [&](int src) -> pair<vector<int>,vector<int>> {
        vector<int> dis(N, -1);
        vector<int> prv(N, -1);
        queue<int> q;
        dis[src] = 0, q.push(src);
        while (!q.empty()) {
            int i = q.front(); q.pop();
            for (auto [j, id]: g[i])
                if (dis[j] == -1)
                    prv[j] = id, dis[j] = dis[i] + 1, q.push(j);
        }
        return { prv, dis };
    };
    ll org = ask(vector<int>(M, 0));
    int pref = 0;
    for (int s = 1 << 20; s; s >>= 1) {
        if (pref+s >= M) continue;
        vector<int> tmp(M);
        for (int i = 0; i < M; i++) tmp[i] = (i < pref+s);
        if (ask(tmp) == org) {
            pref += s;
        }
    }
    assert(pref < M);
    auto [p1, d1] = bfs(U[pref]);
    auto [p2, d2] = bfs(V[pref]);
    debug(U[pref], V[pref]);
    pary(all(d1));
    pary(all(d2));

    vector<int> t1, t2;
    vector<int> span_tree(M, 1);
    span_tree[pref] = 0;
    for (int i = 0; i < N; i++)
        if (d1[i] != d2[i]) {
            if (i == U[pref] || i == V[pref]) continue;
            if (d1[i] < d2[i]) {
                span_tree[p1[i]] = 0;
                t1.push_back(i);
            } else {
                span_tree[p2[i]] = 0;
                t2.push_back(i);
            }
        }
    pary(all(span_tree));
    assert(ask(span_tree) == org);

    int sid = 0;
    if (t1.empty()) sid = U[pref];
    else {
        sort(all(t1), [&](int u, int v){ return d1[u] > d1[v]; });
        for (int s = 1 << 20; s; s >>= 1) {
            if (sid + s >= t1.size()) continue;
            auto tmp = span_tree;
            for (int i = 0; i < t1.size(); i++) if (i < sid + s) tmp[p1[t1[i]]] = 1;
            if (ask(tmp) == org) {
                sid += s;
            }
        }
        debug(sid);
        sid = t1[sid];
    }
    debug(sid);
    int tid = 0;
    if (t2.empty()) tid = V[pref];
    else {
        sort(all(t2), [&](int u, int v){ return d2[u] > d2[v]; });
        for (int s = 1 << 20; s; s >>= 1) {
            if (tid + s >= t2.size()) continue;
            auto tmp = span_tree;
            for (int i = 0; i < t2.size(); i++) if (i < tid + s) tmp[p2[t2[i]]] = 1;
            if (ask(tmp) == org) {
                tid += s;
            }
        }
        tid = t2[tid];
    }
    answer(sid, tid);
    debug(A, B);
}

Compilation message (stderr)

highway.cpp: In lambda function:
highway.cpp:40:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |             for (auto [j, id]: g[i])
      |                       ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:57:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     auto [p1, d1] = bfs(U[pref]);
      |          ^
highway.cpp:58:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     auto [p2, d2] = bfs(V[pref]);
      |          ^
highway.cpp:85:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             if (sid + s >= t1.size()) continue;
      |                 ~~~~~~~~^~~~~~~~~~~~
highway.cpp:87:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             for (int i = 0; i < t1.size(); i++) if (i < sid + s) tmp[p1[t1[i]]] = 1;
      |                             ~~^~~~~~~~~~~
highway.cpp:101:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             if (tid + s >= t2.size()) continue;
      |                 ~~~~~~~~^~~~~~~~~~~~
highway.cpp:103:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             for (int i = 0; i < t2.size(); i++) if (i < tid + s) tmp[p2[t2[i]]] = 1;
      |                             ~~^~~~~~~~~~~

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