oj.uz

Submission #971769

# Submission time Handle Problem Language Result Execution time Memory
971769 2024-04-29T09:14:09 Z fve5 Highway Tolls (IOI18_highway) C++17
51 / 100
 140 ms 11544 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    assert(M + 1 == N);

    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[U[i]].emplace_back(V[i], i);
        adj[V[i]].emplace_back(U[i], i);
    }

    vector<pair<int, int>> dfs_order;
    auto dfs = [&](auto &&dfs, int node, int par) -> void {
        for (auto [x, idx]: adj[node]) {
            if (x == par) continue;
            dfs_order.emplace_back(x, idx);
            dfs(dfs, x, node);
        }
    };

    long long base_cost = ask(vector<int>(M));

    int S, T;

    { // Get S
        dfs_order.clear();
        dfs(dfs, 0, -1);

        int l = 0, r = N;
        while (l + 1 < r) {
            int m = (l + r) / 2;

            vector<int> query(M);
            for (int i = 0; i < m; i++) query[dfs_order[i].second] = 1;

            if (ask(query) == base_cost / A * B) r = m;
            else l = m;
        }

        S = dfs_order[r - 1].first;
    }

    { // Get T
        dfs_order.clear();
        dfs(dfs, S, -1);

        int l = 0, r = N;
        while (l + 1 < r) {
            int m = (l + r) / 2;

            vector<int> query(M);
            for (int i = 0; i < m; i++) query[dfs_order[i].second] = 1;

            if (ask(query) == base_cost / A * B) r = m;
            else l = m;
        }

        T = dfs_order[r - 1].first;
    }

    answer(S, T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 0 ms 444 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 444 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 9 ms 1780 KB Output is correct
3 Correct 107 ms 8980 KB Output is correct
4 Correct 87 ms 9004 KB Output is correct
5 Correct 80 ms 9048 KB Output is correct
6 Correct 93 ms 9012 KB Output is correct
7 Correct 101 ms 8856 KB Output is correct
8 Correct 85 ms 8880 KB Output is correct
9 Correct 117 ms 9016 KB Output is correct
10 Correct 111 ms 8852 KB Output is correct
11 Correct 105 ms 9204 KB Output is correct
12 Correct 107 ms 9428 KB Output is correct
13 Correct 87 ms 9284 KB Output is correct
14 Correct 125 ms 9340 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1808 KB Output is correct
2 Correct 13 ms 3096 KB Output is correct
3 Correct 21 ms 4148 KB Output is correct
4 Correct 111 ms 11120 KB Output is correct
5 Correct 64 ms 11120 KB Output is correct
6 Correct 98 ms 11132 KB Output is correct
7 Correct 74 ms 11120 KB Output is correct
8 Correct 77 ms 11544 KB Output is correct
9 Correct 74 ms 11116 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 13 ms 1528 KB Output is correct
3 Correct 93 ms 7088 KB Output is correct
4 Correct 89 ms 8872 KB Output is correct
5 Correct 90 ms 8860 KB Output is correct
6 Correct 126 ms 8964 KB Output is correct
7 Correct 83 ms 9096 KB Output is correct
8 Correct 102 ms 9232 KB Output is correct
9 Correct 127 ms 9476 KB Output is correct
10 Correct 87 ms 8852 KB Output is correct
11 Correct 122 ms 8776 KB Output is correct
12 Correct 105 ms 9360 KB Output is correct
13 Correct 105 ms 9368 KB Output is correct
14 Correct 88 ms 9332 KB Output is correct
15 Correct 71 ms 8872 KB Output is correct
16 Correct 94 ms 8856 KB Output is correct
17 Correct 140 ms 9092 KB Output is correct
18 Correct 87 ms 9000 KB Output is correct
19 Correct 116 ms 9012 KB Output is correct
20 Correct 79 ms 9844 KB Output is correct
21 Correct 63 ms 9332 KB Output is correct
22 Correct 65 ms 9312 KB Output is correct
23 Correct 67 ms 9264 KB Output is correct
24 Correct 98 ms 9248 KB Output is correct
25 Correct 87 ms 10856 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -