Submission #1211302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211302		SpyrosAliv	통행료 (IOI18_highway)	C++20	51 / 100	293 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, int reqDep) {
    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;
    if (reqDep == -1) {
        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;
        }
    }
    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;
    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;
    int ff = find_second(0, -1);
    vector<int> q(n-1, 0);
    ll reqDep = ask(q) / (ll)a;
    answer(ff, find_second(ff, reqDep));
}

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