Submission #499654

#	Time	Username	Problem	Language	Result	Execution time	Memory
499654		CatalinT	Highway Tolls (IOI18_highway)	C++17	51 / 100	323 ms	262148 KiB

highway

#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <cassert>
#include <iomanip>
#include <cmath>
#include <bitset>
 
using namespace std;

#include "highway.h"

using int64 = long long;

// cache

map<pair<int, int>, int> eidx;

int eget(int u, int v) {
    if (u > v) swap(u, v);
    return eidx[{u, v}];
}

void eset(int u, int v, int idx) {
    if (u > v) swap(u, v);
    eidx[{u, v}] = idx;
}

//

vector<vector<int>> adj;

vector<int> dist;
vector<int> par;

void dfs(int n, int p) {
    for (int v : adj[n]) {
        if (v != p) {
            dist[v] = dist[n] + 1;
            par[v] = n;
            dfs(v, n);
        }
    }
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int M = U.size();
    int S = -1;
    int T = -1;
    // Step 0. Find min dist, 1 query

    vector<int> w(M);
    int64 D = ask(w) / A;

    // Step 1. Find edge on min - path, 18 queries worst-case (!)

    int l = 0, r = M - 1, sol = -1;

    while (l <= r) {
        int m = (l + r) >> 1;

        w.assign(M, 0);
        for (int i = 0; i <= m; i++)
            w[i] = 1;

        int64 cur = ask(w);

        if (cur > D * A) {
            sol = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    assert(sol != -1);

    cerr << "Critical edge: " << U[sol] << " -> " << V[sol] << "\n";

    // 51 points, tree
    adj.assign(N, vector<int>{});
    
    for (int i = 0; i < M; i++) {
        adj[ U[i] ].push_back( V[i] );
        adj[ V[i] ].push_back( U[i] );
        eset(U[i], V[i], i);
    }

    auto solve_half_tree = [&] (int x, int y, int & R) {
        R = -1;

        cerr << "solve_half_tree, start: " << x << " par: " << y << "\n";

        dist.assign(N, 0);
        par.assign(N, -1);
        dfs(x, y);

        w.assign(M, 0);

        for (int i = 0; i < N; i++) {
            if (par[i] != -1) {
                w[eget(i, par[i])] = 1;
            }
        }

        int64 depth = ask(w);

        bool ok = false;
        for (int i = 0; i < N; i++) {
            if ((int64)i * B + (int64)(D - i) * A == depth) {
                depth = i;
                ok = true;
                break;
            }
        }
        assert(ok);

        cerr << "depth: " << depth << "\n";

        if (!depth) {
            R = x;
        } else {
            vector<int> cand;
            for (int i = 0; i < N; i++) {
                if (par[i] != -1 && dist[i] == depth) {
                    cand.push_back(i);
                }
            }
            assert(cand.size());

            function<int(int, int)> rec = [&] (int l, int r) {
                if (l == r) {
                    return cand[l];
                }

                int m = (l + r) >> 1;

                vector<int> w(M);

                for (int i = l; i <= m; i++) {
                    w[eget(cand[i], par[cand[i]])] = 1;
                }

                bool ok = ask(w) > D * A;

                if (ok) {
                    return rec(l, m);
                } else {
                    return rec(m + 1, r);
                }
            };

            R = rec(0, cand.size() - 1);
        };
    };

    solve_half_tree(U[sol], V[sol], S);
    solve_half_tree(V[sol], U[sol], T);

    cerr << S << " " << T << "\n";

    assert(S != T);

    answer(S, T);
}

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