Submission #1044719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044719		RecursiveCo	Highway Tolls (IOI18_highway)	C++17	51 / 100	87 ms	18412 KiB

highway

#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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31