Submission #554706

#	Time	Username	Problem	Language	Result	Execution time	Memory
554706		maomao90	Highway Tolls (IOI18_highway)	C++17	18 / 100	248 ms	262144 KiB

highway

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;
#include "highway.h"

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005

int n, m;
vii adj[MAXN];
int a, b;
ll itoll;
vi w;

vi leaves;
ii p[MAXN];
int l[MAXN];
int pre[MAXN], pst[MAXN], ptr;
void dfs(int u) {
    pre[u] = ptr++;
    bool leaf = 1;
    for (auto [v, i] : adj[u]) {
        if (v == p[u].FI) continue;
        leaf = 0;
        p[v] = {u, i};
        l[v] = l[u] + 1;
        dfs(v);
    }
    if (leaf) {
        leaves.pb(u);
    }
    pst[u] = ptr;
}

void findst(int u, int tl) {
    if (l[u] == tl) {
        leaves.pb(u);
        return;
    }
    for (auto [v, i] : adj[u]) {
        if (v == p[u].FI) continue;
        findst(v, tl);
    }
}

int bstaLeaves(int x = -1) {
    int lo = 0, hi = leaves.size() - 1, mid;
    while (lo < hi) {
        w = vi(m, 0);
        mid = lo + hi >> 1;
        REP (i, lo, mid + 1) {
            int u = leaves[i];
            while (p[u].FI != -1) {
                if (w[p[u].SE] == 1) {
                    break;
                }
                w[p[u].SE] = 1;
                u = p[u].FI;
            }
        }
        ll toll = ask(w);
        int delta = (toll - itoll) / (b - a);
        if ((x == -1 && toll != itoll) || delta == x) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return leaves[lo];
}

void find_pair(int N, vi U, vi V, int A, int B) {
    n = N, m = U.size();
    a = A, b = B;
    REP (i, 0, m) {
        adj[U[i]].pb({V[i], i});
        adj[V[i]].pb({U[i], i});
    }
    p[0] = {-1, -1};
    dfs(0);
    w = vi(m, 0);
    itoll = ask(w);
    int dis = itoll / a;
    int s = bstaLeaves();
    int lo = 0, hi = l[s] - 1, mid;
    while (lo < hi) {
        mid = lo + hi + 1 >> 1;
        int u = s;
        while (l[u] > mid) {
            u = p[u].FI;
        }
        vi w(m, 0);
        while (p[u].FI != -1) {
            w[p[u].SE] = 1;
            u = p[u].FI;
        }
        ll toll = ask(w);
        if (toll == itoll) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    int lca = s;
    int nxt = s;
    while (l[lca] > lo) {
        nxt = lca;
        lca = p[lca].FI;
    }
    w = vi(m, 0);
    REP (i, 0, n) {
        if (pre[nxt] <= pre[i] && pre[i] < pst[nxt]) {
            w[p[i].SE] = 1;
        }
    }
    ll toll = ask(w);
    int ldis = (toll - itoll) / (b - a);
    int rdis = dis - ldis;
    cerr << lca << ' ' << ldis << ' ' << rdis << '\n';
    leaves.clear();
    for (auto [v, i] : adj[lca]) {
        if (v == p[lca].FI || v == nxt) continue;
        findst(v, l[lca] + rdis);
    }
    int t = -1;
    if (leaves.empty()) {
        t = lca;
    } else {
        t = bstaLeaves(rdis);
    }
    leaves.clear();
    findst(nxt, l[lca] + ldis);
    assert(!leaves.empty());
    s = bstaLeaves(ldis);
    cerr << s << ' ' << t << '\n';
    answer(s, t);
}

Compilation message (stderr)

highway.cpp: In function 'int bstaLeaves(int)':
highway.cpp:79:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |         mid = lo + hi >> 1;
      |               ~~~^~~~
highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:116:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |         mid = lo + hi + 1 >> 1;
      |               ~~~~~~~~^~~

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