Submission #554677

#	Time	Username	Problem	Language	Result	Execution time	Memory
554677		maomao90	Highway Tolls (IOI18_highway)	C++17	6 / 100	302 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];
void dfs(int u) {
    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);
    }
}

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 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);
        if (toll != itoll) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return leaves[lo];
}

void find_pair(int N, vi U, vi V, int A, int B) {
    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();
    w = vi(m, 0);
    int u = s;
    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);
    assert((toll - itoll) % (b - a) == 0);
    int ldis = (toll - itoll) / (b - a);
    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;
    while (l[lca] > lo) {
        lca = p[lca].FI;
    }
    while (l[s] > l[lca] + ldis) {
        s = p[s].FI;
    }
    assert(l[s] == l[lca] + ldis);
    int rdis = dis - ldis;
    leaves.clear();
    findst(lca, l[lca] + rdis);
    int t = bstaLeaves();
    answer(s, t);
}

Compilation message (stderr)

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

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