oj.uz

Submission #1044719

# Submission time Handle Problem Language Result Execution time Memory
1044719 2024-08-05T12:47:00 Z RecursiveCo Highway Tolls (IOI18_highway) C++17
51 / 100
 87 ms 18412 KB 
#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

#define out(o) cout << o

vector<vector<pair<int, int>>> adjList;
vector<int> parent;
vector<vector<int>> level;

void dfs(int v, int p, int i, int l) {
    parent[v] = i;
    level[l].push_back(v);
    for (auto con: adjList[v]) {
        if (con.first == p) continue;
        dfs(con.first, v, con.second, l + 1);
    }
}

vector<int> correct;
vector<int> upward;
int d;

void comp(int v, int p, int i, int h) {
    if (h == d) {
        correct.push_back(v);
        upward.push_back(i);
    }
    for (auto con: adjList[v]) {
        if (con.first == p) continue;
        comp(con.first, v, con.second, h + 1);
    }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size(); // = V.size(); assumed to be N - 1
    adjList.resize(N);
    parent.resize(N);
    level.resize(N);
    for (int i = 0; i < M; i++) {
        int a = U[i];
        int b = V[i];
        adjList[a].push_back({b, i});
        adjList[b].push_back({a, i});
    }
    vector<int> W(N - 1, 0);
    long long dw = ask(W);
    d = (int) (dw / ((long long) A));
    dfs(0, -1, -1, 0);
    int l = 1;
    int r = N;
    while (r - l > 1) {
        int middle = (l + r) / 2;
        vector<int> W(N - 1, 0);
        for (int le = middle; le < N; le++) for (int node: level[le]) W[parent[node]] = 1;
        long long here = ask(W);
        if (here > dw) l = middle;
        else r = middle;
    }
    int HEIGHT = l;
    l = 0;
    r = level[HEIGHT].size();
    while (r - l >= 1) {
        int middle = (l + r) / 2;
        vector<int> W(N - 1, 0);
        for (int i = 0; i <= middle; i++) W[parent[level[HEIGHT][i]]] = 1;
        long long here = ask(W);
        if (here > dw) r = middle;
        else l = middle + 1;
    }
    int first = level[HEIGHT][l];
    comp(first, -1, -1, 0);
    l = 0;
    r = correct.size();
    while (r - l >= 1) {
        int middle = (l + r) / 2;
        vector<int> W(N - 1, 0);
        for (int i = 0; i <= middle; i++) W[upward[i]] = 1;
        long long here = ask(W);
        if (here > dw) r = middle;
        else l = middle + 1;
    }
    int second = correct[l];
    answer(first, second);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 8 ms 1528 KB Output is correct
3 Correct 72 ms 11212 KB Output is correct
4 Correct 68 ms 11292 KB Output is correct
5 Correct 68 ms 11140 KB Output is correct
6 Correct 69 ms 11244 KB Output is correct
7 Correct 66 ms 11232 KB Output is correct
8 Correct 71 ms 11196 KB Output is correct
9 Correct 81 ms 11184 KB Output is correct
10 Correct 71 ms 11028 KB Output is correct
11 Correct 76 ms 12192 KB Output is correct
12 Correct 82 ms 13132 KB Output is correct
13 Correct 87 ms 12376 KB Output is correct
14 Correct 80 ms 12296 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2388 KB Output is correct
2 Correct 15 ms 4304 KB Output is correct
3 Correct 19 ms 6288 KB Output is correct
4 Correct 65 ms 18396 KB Output is correct
5 Correct 58 ms 18396 KB Output is correct
6 Correct 57 ms 18396 KB Output is correct
7 Correct 59 ms 18256 KB Output is correct
8 Correct 60 ms 18396 KB Output is correct
9 Correct 66 ms 18412 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 1532 KB Output is correct
3 Correct 51 ms 8656 KB Output is correct
4 Correct 66 ms 10992 KB Output is correct
5 Correct 63 ms 11028 KB Output is correct
6 Correct 79 ms 11304 KB Output is correct
7 Correct 64 ms 11032 KB Output is correct
8 Correct 65 ms 11020 KB Output is correct
9 Correct 70 ms 11372 KB Output is correct
10 Correct 70 ms 11208 KB Output is correct
11 Correct 68 ms 11864 KB Output is correct
12 Correct 74 ms 13092 KB Output is correct
13 Correct 72 ms 12464 KB Output is correct
14 Correct 73 ms 13016 KB Output is correct
15 Correct 77 ms 11008 KB Output is correct
16 Correct 69 ms 11032 KB Output is correct
17 Correct 79 ms 12736 KB Output is correct
18 Correct 65 ms 12416 KB Output is correct
19 Correct 65 ms 11004 KB Output is correct
20 Correct 68 ms 13692 KB Output is correct
21 Correct 60 ms 12104 KB Output is correct
22 Correct 64 ms 12144 KB Output is correct
23 Correct 73 ms 12092 KB Output is correct
24 Correct 73 ms 12600 KB Output is correct
25 Correct 81 ms 17456 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1368 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1368 KB Incorrect
2 Halted 0 ms 0 KB -