Submission #1211416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211416		SpyrosAliv	Highway Tolls (IOI18_highway)	C++20	0 / 100	5 ms	2020 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;
vector<bool> vis, backEdge;
int n, m, a, b, maxD;
ll reqDep, init;

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

void reroot(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 || backEdge[lab]) continue;
        edgeLab[next] = lab;
        reroot(next, node, d+1);
    }
}

int find_second(int root, int needRoot = 1) {
    if (needRoot == 1) {
        par.assign(n, 0);
        dep.assign(n, 0);
        edgeLab.assign(n, 0);
        maxD = 0;
        prec(root, 0);
    }
    vector<int> q;
    q.assign(m, 1);
    for (int i = 0; i < n; i++) {
        if (i == root) continue;
        q[edgeLab[i]] = 0;
    }
    if (init == -1) init = ask(q);
    int lo = 1, hi = maxD;
    int secDep = 0;
    if (reqDep == -1) {
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            fill(q.begin(), q.end(), 1);
            for (int i = 0; i < n; i++) {
                if (i == root) continue;
                if (dep[i] >= mid) {
                    q[edgeLab[i]] = 1;
                }
                else q[edgeLab[i]] = 0;
            }
            ll ret = ask(q);
            if (ret != init) {
                secDep = mid;
                lo = mid+1;
            }
            else hi = mid-1;
        }
    }
    else secDep = reqDep;
    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;
    m = U.size();
    tree.clear();
    tree.resize(n);
    backEdge.assign(m, false);
    for (int i = 0; i < m; i++) {
        tree[U[i]].push_back({V[i], i});
        tree[V[i]].push_back({U[i], i});
    }
    vis.assign(n, false);
    init = -1;
    a = A;
    b = B;
    int ff = find_second(0);
    ll reqDep = init / (ll)a;
    reroot(ff);
    answer(ff, find_second(ff, 0));
}

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