oj.uz

Submission #1068552

# Submission time Handle Problem Language Result Execution time Memory
1068552 2024-08-21T10:35:44 Z TheQuantiX Highway Tolls (IOI18_highway) C++17
51 / 100
 236 ms 34616 KB 
#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];
vector<ll> dist[90000];
ll mxd = 0;

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

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    map< pair<ll, ll>, ll > mp;
    pair<ll, ll> p = {-1, -1};
    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});
        mp[{U[i], V[i]}] = i;
        mp[{V[i], U[i]}] = i;
    }
    vector<int> w(n - 1, 1);
    ll dst = ask(w) / B;
    dfs(0, -1, 0);
    for (int i = 0; i < n - 1; i++) {
        if (par[U[i]] == V[i]) {
            swap(U[i], V[i]);
        }
    }
    ll l = 0, r = mxd;
    while (r > l) {
        ll mid = (r + l) / 2;
        w.assign(n - 1, 0);
        for (int i = 0; i <= mid; i++) {
            for (int j : dist[i]) {
                w[j] = 1;
            }
        }
        if (ask(w) == dst * B) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    ll elow = l;
    w.assign(n - 1, 0);
    for (int i = 0; i <= l; i++) {
        for (int j : dist[i]) {
            w[j] = 1;
        }
    }
    l = 0;
    r = dist[elow].size() - 1;
    while (r > l) {
        ll mid = (r + l) / 2;
        w.assign(n - 1, 0);
        for (int i = 0; i <= mid; i++) {
            w[dist[elow][i]] = 1;
        }
        // cout << mid << ' ' << dst * B << ' ' << ask(w) << ' ' << (B - A) << ' ' << (elow - mid + 1) << '\n';
        if (ask(w) != dst * A) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    } 
    p.second = V[dist[elow][l]];
    w.assign(n - 1, 0);
    ll e = p.second;
    while (e != 0) {
        w[mp[{e, par[e]}]] = 1;
        e = par[e];
    }
    if (ask(w) == dst * B) {
        e = p.second;
        for (int i = 0; i < dst; i++) {
            e = par[e];
        }
        p.first = e;
        answer(p.first, p.second);
        return;
    }
    ord.clear();
    for (int i = 0; i < mxd; i++) {
        dist[i].clear();
    }
    mxd = 0;
    dfs(p.second, -1, 0);
    for (int i = 0; i < n - 1; i++) {
        if (par[U[i]] == V[i]) {
            swap(U[i], V[i]);
        }
    }
    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) >= dst * B) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    p.first = V[ord[l]];
    // cout << p.first << ' ' << p.second << '\n';
    answer(p.first, p.second);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 2 ms 5336 KB Output is correct
3 Correct 1 ms 5204 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 2 ms 5208 KB Output is correct
6 Correct 1 ms 5208 KB Output is correct
7 Correct 1 ms 5208 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5208 KB Output is correct
10 Correct 1 ms 5208 KB Output is correct
11 Correct 1 ms 5208 KB Output is correct
12 Correct 2 ms 5208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5464 KB Output is correct
2 Correct 14 ms 7512 KB Output is correct
3 Correct 170 ms 24780 KB Output is correct
4 Correct 158 ms 24804 KB Output is correct
5 Correct 158 ms 24884 KB Output is correct
6 Correct 175 ms 24732 KB Output is correct
7 Correct 168 ms 24852 KB Output is correct
8 Correct 159 ms 24844 KB Output is correct
9 Correct 150 ms 24636 KB Output is correct
10 Correct 190 ms 24848 KB Output is correct
11 Correct 162 ms 26988 KB Output is correct
12 Correct 192 ms 28168 KB Output is correct
13 Correct 161 ms 27068 KB Output is correct
14 Correct 171 ms 26352 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8536 KB Output is correct
2 Correct 22 ms 11728 KB Output is correct
3 Correct 35 ms 15100 KB Output is correct
4 Correct 109 ms 34596 KB Output is correct
5 Correct 95 ms 34568 KB Output is correct
6 Correct 108 ms 34616 KB Output is correct
7 Correct 108 ms 34616 KB Output is correct
8 Correct 120 ms 34608 KB Output is correct
9 Correct 105 ms 34612 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5464 KB Output is correct
2 Correct 14 ms 7664 KB Output is correct
3 Correct 123 ms 20908 KB Output is correct
4 Correct 175 ms 24988 KB Output is correct
5 Correct 168 ms 24752 KB Output is correct
6 Correct 159 ms 25148 KB Output is correct
7 Correct 146 ms 24844 KB Output is correct
8 Correct 176 ms 24832 KB Output is correct
9 Correct 189 ms 24964 KB Output is correct
10 Correct 174 ms 24992 KB Output is correct
11 Correct 199 ms 27160 KB Output is correct
12 Correct 209 ms 28492 KB Output is correct
13 Correct 170 ms 27464 KB Output is correct
14 Correct 180 ms 27936 KB Output is correct
15 Correct 155 ms 24796 KB Output is correct
16 Correct 160 ms 24752 KB Output is correct
17 Correct 230 ms 27852 KB Output is correct
18 Correct 199 ms 28152 KB Output is correct
19 Correct 175 ms 25088 KB Output is correct
20 Correct 190 ms 28804 KB Output is correct
21 Correct 160 ms 27136 KB Output is correct
22 Correct 170 ms 27260 KB Output is correct
23 Correct 184 ms 26008 KB Output is correct
24 Correct 184 ms 26888 KB Output is correct
25 Correct 236 ms 33740 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 7256 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 7256 KB Incorrect
2 Halted 0 ms 0 KB -