Submission #1211278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211278		SpyrosAliv	Highway Tolls (IOI18_highway)	C++20	12 / 100	289 ms	327680 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<vector<pair<int, int>>> tree;
vector<int> par, dep, edgeLab;
int n, a, b, maxD;

void prec(int node, int p = 0, int d = 0) {
    par[node] = p;
    dep[node] = d;
    maxD = max(maxD, d);
    for (auto [next, lab]: tree[node]) {
        if (next == p) continue;
        edgeLab[next] = lab;
        prec(next, node, d+1);
    }
}

int find_second(int root) {
    par.assign(n, 0);
    dep.assign(n, 0);
    edgeLab.assign(n, 0);
    maxD = 0;
    prec(root, 0);
    vector<int> q;
    q.assign(n-1, 0);
    ll init = ask(q);
    int lo = 1, hi = maxD;
    int secDep = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        fill(q.begin(), q.end(), 0);
        for (int i = 0; i < n; i++) {
            if (dep[i] >= mid) {
                q[edgeLab[i]] = 1;
            }
        }
        ll ret = ask(q);
        if (ret != init) {
            secDep = mid;
            lo = mid+1;
        }
        else hi = mid-1;
    }
    vector<int> cands;
    for (int i = 0; i < n; i++) {
        if (dep[i] == secDep) cands.push_back(i);
    }
    int sz = cands.size();
    lo = 0, hi = sz-1;
    int fin = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        fill(q.begin(), q.end(), 0);
        for (int i = 0; i <= mid; i++) {
            q[edgeLab[cands[i]]] = 1;
        }
        ll ret = ask(q);
        if (ret != init) {
            fin = mid;
            hi = mid-1;
        }
        else lo = mid+1;
    }
    return cands[fin];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    n = N;
    tree.clear();
    tree.resize(n);
    for (int i = 0; i < n-1; i++) {
        tree[U[i]].push_back({V[i], i});
        tree[V[i]].push_back({U[i], i});
    }
    a = A;
    b = B;
    answer(0, find_second(0));
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31