Submission #1068251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068251		Ignut	Highway Tolls (IOI18_highway)	C++17	51 / 100	450 ms	262144 KiB

highway

// Ignut

#include "highway.h"
#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 parent[MAXN];

int maxDepth = 0;

void dfs(int v, int par, int d) {
    depth[v] = d;
    parent[v] = par;
    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;
    // cerr << "from " << lo << " to " << hi << '\n';
    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);
        // cerr << mid << " : " << val << " vs " << da + 1ll * (du - mid) * (B - A) << '\n';
        if (val == da)
            lo = mid;
        else
            hi = mid - 1;
    }
    int dv = lo + (dist - (du - 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;
    // cerr << "hi2 = " << hi2 << '\n';
    lo = 0, hi = eu.size() - 1;
    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);
            // cerr << "hi2 min= " << mid << '\n';
        }
        // cerr << mid << " : " << val << " vs " << da << '\n';
        // for (int val : w) cerr << val;
        // cerr << '\n';
        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]];
    // for (int ind : eu) {
    //     cerr << U[ind] << " -> " << V[ind] << '\n';
    // }
    cerr << "U = " << u << "(" << lo << ")\n";

    cerr << du << ' ' << dv << ' ' << dist << '\n';

    int bad = u;
    while (depth[bad] > dv) bad = parent[bad];

    // finding v
    int v;
    if (du - dv == dist) {
        // just vertical
        // look down
        // cerr << "VERTICAL\n";
        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 (U[i] == bad || V[i] == bad) continue;
            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;
        }
        needVal = da;
        // cerr << needVal << '\n';
        // cerr << lo << " -- " << hi << '\n';
        // cout << "hi2 = " << hi2 << '\n';
        // answer(-1, -1); return;
        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);
            // cerr << mid << " ::: " << val << ' ' << needVal << '\n';
            if (val > needVal)
                hi = mid;
            else
                lo = mid + 1;
        }
        if (depth[U[ev[lo]]] == dv) v = U[ev[lo]];
        else v = V[ev[lo]];
        for (int ind : ev) {
            cerr << U[ind] << " -> " << V[ind] << '\n';
        }
        cerr << "V = " << v << "(" << lo << ")\n";
    }

    cerr << "DEPTH[18] = " << depth[18] << '\n';

    // cerr << "DEPTH[18] = " << depth[56] << '\n';

    answer(u, v);
    return;
}

/*
4, [0, 0, 0, 1], [1, 2, 3, 2], 1, 3)
4 4 1 3 1 3
0 1
0 2
0 3
1 2

N M  A B  S T

tree:
4 3  1 2  3 2
0 1
0 2
1 3
*/


// namespace {

// constexpr int MAX_NUM_CALLS = 100;
// constexpr long long INF = 1LL << 61;

// int N, M, A, B, S, T;
// std::vector<int> U, V;
// std::vector<std::vector<std::pair<int, int>>> graph;

// bool answered, wrong_pair;
// int num_calls;

// int read_int() {
//   int x;
//   if (scanf("%d", &x) != 1) {
//     fprintf(stderr, "Error while reading input\n");
//     exit(1);
//   }
//   return x;
// }

// void wrong_answer(const char *MSG) {
//   printf("Wrong Answer: %s\n", MSG);
//   exit(0);
// }

// }  // namespace

// long long ask(const std::vector<int> &w) {
//   if (++num_calls > MAX_NUM_CALLS) {
//     wrong_answer("more than 100 calls to ask");
//   }
//   if (w.size() != (size_t)M) {
//     wrong_answer("w is invalid");
//   }
//   for (size_t i = 0; i < w.size(); ++i) {
//     if (!(w[i] == 0 || w[i] == 1)) {
//       wrong_answer("w is invalid");
//     }
//   }

//   std::vector<bool> visited(N, false);
//   std::vector<long long> current_dist(N, INF);
//   std::queue<int> qa, qb;
//   qa.push(S);
//   current_dist[S] = 0;
//   while (!qa.empty() || !qb.empty()) {
//     int v;
//     if (qb.empty() ||
//         (!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
//       v = qa.front();
//       qa.pop();
//     } else {
//       v = qb.front();
//       qb.pop();
//     }
//     if (visited[v]) {
//       continue;
//     }
//     visited[v] = true;
//     long long d = current_dist[v];
//     if (v == T) {
//       return d;
//     }
//     for (auto e : graph[v]) {
//       int vv = e.first;
//       int ei = e.second;
//       if (!visited[vv]) {
//         if (w[ei] == 0) {
//           if (current_dist[vv] > d + A) {
//             current_dist[vv] = d + A;
//             qa.push(vv);
//           }
//         } else {
//           if (current_dist[vv] > d + B) {
//             current_dist[vv] = d + B;
//             qb.push(vv);
//           }
//         }
//       }
//     }
//   }
//   return -1;
// }

// void answer(int s, int t) {
//   if (answered) {
//     wrong_answer("answered not exactly once");
//   }

//   if (!((s == S && t == T) || (s == T && t == S))) {
//     wrong_pair = true;
//   }

//   answered = true;
// }

// int main() {
//   N = read_int();
//   M = read_int();
//   A = read_int();
//   B = read_int();
//   S = read_int();
//   T = read_int();
//   U.resize(M);
//   V.resize(M);
//   graph.assign(N, std::vector<std::pair<int, int>>());
//   for (int i = 0; i < M; ++i) {
//     U[i] = read_int();
//     V[i] = read_int();
//     graph[U[i]].push_back({V[i], i});
//     graph[V[i]].push_back({U[i], i});
//   }

//   answered = false;
//   wrong_pair = false;
//   num_calls = 0;
//   find_pair(N, U, V, A, B);
//   if (!answered) {
//     wrong_answer("answered not exactly once");
//   }
//   if (wrong_pair) {
//     wrong_answer("{s, t} is wrong");
//   }
//   printf("Accepted: %d\n", num_calls);
//   return 0;
// }

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