Submission #1068296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1068296	2024-08-21T09:08:50 Z	TheQuantiX	Highway Tolls (IOI18_highway)	C++17	6 / 100	85 ms	17352 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	2392 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	2392 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	4180 KB	Output is correct
2	Correct	17 ms	5852 KB	Output is correct
3	Correct	29 ms	7376 KB	Output is correct
4	Correct	77 ms	17116 KB	Output is correct
5	Correct	85 ms	17072 KB	Output is correct
6	Correct	67 ms	17108 KB	Output is correct
7	Correct	80 ms	17352 KB	Output is correct
8	Correct	64 ms	17108 KB	Output is correct
9	Correct	68 ms	17120 KB	Output is correct