Submission #1068112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068112		Ignut	Highway Tolls (IOI18_highway)	C++17	Compilation error	0 ms	0 KiB

highway

// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll ask(vector<int> w);

void answer(int s, int t);

const int MAXN = 9e4 + 123;
int n;

vector<int> tree[MAXN];
int depth[MAXN];

int maxDepth = 0;

void dfs(int v, int par, int d) {
    depth[v] = d;
    maxDepth = max(maxDepth, d);
    for (int to : tree[v])
        if (to != par)
            dfs(to, v, d + 1);
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    for (int i = 0; i < M; i ++) {
        tree[U[i]].push_back(V[i]);
        tree[V[i]].push_back(U[i]);
    }
    dfs(0, -1, 0);

    vector<int> w(M, 0);
    ll da = ask(w);
    int dist = ask(w) / (1ll * A);
    // bigger depth -- u
    int lo = 0, hi = maxDepth;
    int lo2 = 0;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        w.assign(M, 0);
        for (int i = 0; i < M; i ++) {
            int d = min(depth[U[i]], depth[V[i]]);
            if (d >= mid)
                w[i] = true;
        }
        ll val = ask(w);
        if (val == 1ll * dist * B)
            lo2 = max(lo2, mid);

        if (val == da)
            hi = mid;
        else
            lo = mid + 1;
    }
    int du = lo;
    // smaller depth -- v
    lo = lo2, hi = du;
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        w.assign(M, 0);
        for (int i = 0; i < M; i ++) {
            int d = max(depth[U[i]], depth[V[i]]);
            if (d <= mid)
                w[i] = true;
        }
        ll val = ask(w);
        if (val == da)
            lo = mid;
        else
            hi = mid - 1;
    }
    int dv = lo;
    // ========================================================== //

    // findind u (lower point)
    vector<int> eu;
    for (int i = 0; i < M; i ++) {
        int d = max(depth[U[i]], depth[V[i]]);
        if (d == du)
            eu.push_back(i);
    }
    int hi2 = n - 1;
    lo = 0, hi = eu.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        w.assign(M, 0);
        for (int i = 0; i < mid; i ++)
            w[eu[i]] = true;
        ll val = ask(w);
        if (val == da - 2 * A + 2 * B)
            hi2 = min(hi2, mid);
        if (val > da)
            hi = mid;
        else
            lo = mid + 1;
    }
    int u;
    if (depth[U[eu[lo]]] == du) u = U[eu[lo]];
    else u = V[eu[lo]];
    
    // finding v
    int v;
    if (du - dv == dist) {
        // just vertical
        // look down
        vector<int> ev;
        for (int i = 0; i < M; i ++) {
            int d = min(depth[U[i]], depth[V[i]]);
            if (d == dv)
                ev.push_back(i);
        }
        lo = 0, hi = ev.size() - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            w.assign(M, 0);
            for (int i = 0; i < mid; i ++)
                w[ev[i]] = true;
            ll val = ask(w);
            if (val > da)
                hi = mid;
            else
                lo = mid + 1;
        }
        if (depth[U[ev[lo]]] == dv) v = U[ev[lo]];
        else v = V[ev[lo]];
    }
    else {
        // normal path (lca != u and lca != v)
        vector<int> ev;
        for (int i = 0; i < M; i ++) {
            int d = max(depth[U[i]], depth[V[i]]);
            if (d == dv)
                ev.push_back(i);
        }
        lo = 0, hi = ev.size() - 1;
        ll needVal = da;
        if (du == dv) {
            hi = min(int(ev.size()) - 1, hi2);
            needVal = needVal - A + B;
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            w.assign(M, 0);
            for (int i = 0; i < mid; i ++)
                w[ev[i]] = true;
            ll val = ask(w);
            if (val > needVal)
                hi = mid;
            else
                lo = mid + 1;
        }
        if (depth[U[ev[lo]]] == dv) v = U[ev[lo]];
        else v = V[ev[lo]];
    }

    answer(u, v);
    return;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccmv9q68.o: in function `find_pair(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)':
highway.cpp:(.text+0x330): undefined reference to `ask(std::vector<int, std::allocator<int> >)'
/usr/bin/ld: highway.cpp:(.text+0x405): undefined reference to `ask(std::vector<int, std::allocator<int> >)'
/usr/bin/ld: highway.cpp:(.text+0x5ad): undefined reference to `ask(std::vector<int, std::allocator<int> >)'
/usr/bin/ld: highway.cpp:(.text+0x755): undefined reference to `ask(std::vector<int, std::allocator<int> >)'
/usr/bin/ld: highway.cpp:(.text+0x9fe): undefined reference to `ask(std::vector<int, std::allocator<int> >)'
/usr/bin/ld: /tmp/ccmv9q68.o:highway.cpp:(.text+0xcce): more undefined references to `ask(std::vector<int, std::allocator<int> >)' follow
collect2: error: ld returned 1 exit status