Submission #566626

#	Time	Username	Problem	Language	Result	Execution time	Memory
566626		hoanghq2004	Highway Tolls (IOI18_highway)	C++14	100 / 100	243 ms	18688 KiB

highway

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "highway.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
    vector <vector <pair <int, int>>> g(n), e(n);
    vector <int> ord(n), id(n, -1);
    int m = U.size();
    for (int i = 0; i < m; ++i) {
        g[U[i]].push_back({V[i], i});
        g[V[i]].push_back({U[i], i});
    }
    int L = 0, R = m - 1;
    vector <int> w(m, 0);
    long long tot = ask(w);
    while (L < R) {
        int mid = L + R >> 1;
        vector <int> w(m, 0);
        for (int i = mid + 1; i < m; ++i) w[i] = 1;
        if (ask(w) != tot) L = mid + 1;
        else R = mid;
    }
    int x = L;
    queue <int> q;
    q.push(U[x]);
    q.push(V[x]);
    vector <int> type(n, -1);
    type[U[x]] = 0;
    type[V[x]] = 1;
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (auto [v, i]: g[u]) {
            if (type[v] != -1) continue;
            type[v] = type[u];
            id[v] = i;
            e[u].push_back({v, i});
            q.push(v);
        }
    }
    int ti = 0;
    function <void(int)> dfs = [&](int u) {
        ord[ti++] = u;
        for (auto [v, i]: e[u]) {
            dfs(v);
        }
    };
    dfs(U[x]);
    w.assign(m, -1);
    for (int i = 0; i < n; ++i) {
        if (i == U[x] || i == V[x]) continue;
        w[id[i]] = 0;
    }
    w[x] = 0;
    for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
    tot = ask(w);
    L = 0, R = ti - 1;
    while (L < R) {
        int mid = L + R >> 1;
        vector <int> w(m, -1);
        for (int i = 0; i <= mid; ++i) {
            if (ord[i] == U[x] || ord[i] == V[x]) continue;
            if (type[ord[i]] == 0) w[id[ord[i]]] = 0;
        }
        for (int i = 0; i < n; ++i) {
            if (i == U[x] || i == V[x]) continue;
            if (type[i] == 1) w[id[i]] = 0;
        }
        w[x] = 0;
        for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
        if (ask(w) == tot) R = mid;
        else L = mid + 1;
    }
    int S = ord[L];
    ti = 0;
    dfs(V[x]);
    L = 0, R = ti - 1;
    while (L < R) {
        int mid = L + R >> 1;
        vector <int> w(m, -1);
        for (int i = 0; i <= mid; ++i) {
            if (ord[i] == U[x] || ord[i] == V[x]) continue;
            if (type[ord[i]] == 1) w[id[ord[i]]] = 0;
        }
        for (int i = 0; i < n; ++i) {
            if (i == U[x] || i == V[x]) continue;
            if (type[i] == 0) w[id[i]] = 0;
        }
        w[x] = 0;
        for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
        if (ask(w) == tot) R = mid;
        else L = mid + 1;
    }
    int T = ord[L];
    answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:26:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         int mid = L + R >> 1;
      |                   ~~^~~
highway.cpp:42:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         for (auto [v, i]: g[u]) {
      |                   ^
highway.cpp: In lambda function:
highway.cpp:53:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |         for (auto [v, i]: e[u]) {
      |                   ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int mid = L + R >> 1;
      |                   ~~^~~
highway.cpp:88:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |         int mid = L + R >> 1;
      |                   ~~^~~

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