Submission #1068296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068296		TheQuantiX	Highway Tolls (IOI18_highway)	C++17	6 / 100	85 ms	17352 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

using namespace std;
using ll = long long;

constexpr ll INF = 1000000000000000000LL;

ll n, m, q, k, x, y;
vector< pair<ll, ll> > G[90000];
vector<ll> ord;
ll par[90000];

void dfs(ll x, ll p) {
    par[x] = p;
    for (auto i : G[x]) {
        if (i.first != p) {
            ord.push_back(i.second);
            dfs(i.first, x);
        }
    }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    n = N;
    for (int i = 0; i < n - 1; i++) {
        G[U[i]].push_back({V[i], i});
        G[V[i]].push_back({U[i], i});
    }
    vector<int> w(n - 1, 1);
    ll dist = ask(w) / B;
    dfs(0, -1);
    for (int i = 0; i < n - 1; i++) {
        if (par[U[i]] == V[i]) {
            swap(U[i], V[i]);
        }
    }
    ll l = 0, r = n - 1;
    while (r > l) {
        ll mid = (r + l) / 2;
        w.assign(n - 1, 0);
        for (int i = 0; i <= mid; i++) {
            w[ord[i]] = 1;
        }
        if (ask(w) > dist * A) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    ll e = l;
    l = 0;
    r = n - 1;
    while (r > l) {
        ll mid = (r + l) / 2;
        w.assign(n - 1, 0);
        for (int i = 0; i <= mid; i++) {
            w[ord[i]] = 1;
        }
        if (ask(w) >= dist * B) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    // cout << e << ' ' << l << '\n';
    ll y = V[e];
    ll x = V[l];
    while (x != -1) {
        if (x == V[e]) {
            y = U[e];
            break;
        }
        x = par[x];
    }
    answer(y, V[l]);
}

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