Submission #556360

#	Time	Username	Problem	Language	Result	Execution time	Memory
556360		maomao90	Highway Tolls (IOI18_highway)	C++17	100 / 100	226 ms	16492 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;
ii eg[MAXN];
vii adj[MAXN];
int a, b;
ll itoll;
vi w;
ii p[MAXN];
int dis[MAXN], comp[MAXN];
bool back[MAXN];

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});
        eg[i] = {U[i], V[i]};
    }
    w = vi(m, 0);
    itoll = ask(w);
    REP (i, 0, m) {
        back[i] = 1;
    }
    int sl = -1, tl;
    {
        int lo = 0, hi = m - 1, mid;
        while (lo < hi) {
            mid = lo + hi >> 1;
            w = vi(m, 0);
            REP (i, 0, mid + 1) {
                w[i] = 1;
            }
            ll toll = ask(w);
            if (toll != itoll) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        tie(sl, tl) = eg[lo];
        back[lo] = 0;
    }
    assert(sl != -1);
    cerr << sl << ' ' << tl << '\n';
    queue<int> q;
    memset(comp, -1, sizeof comp);
    REP (i, 0, n) {
        dis[i] = INF;
    }
    dis[sl] = 0;
    comp[sl] = sl;
    q.push(sl);
    dis[tl] = 0;
    comp[tl] = tl;
    q.push(tl);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, i] : adj[u]) {
            if (mnto(dis[v], dis[u] + 1)) {
                back[i] = 0;
                q.push(v);
                p[v] = {u, i};
                comp[v] = comp[u];
            }
        }
    }
    REP (i, 0, m) {
        if (dis[eg[i].FI] < dis[eg[i].SE]) {
            swap(eg[i].FI, eg[i].SE);
        }
        if (back[i]) {
            cerr << "back " << i << '\n';
        }
    }
    int s = -1, t = -1;
    REP (z, 0, 2) {
        vi pot;
        REP (i, 0, n) {
            if (i != sl && comp[i] == sl) {
                pot.pb(i);
            }
        }
        sort(ALL(pot), [&] (int l, int r) {
                return dis[l] < dis[r];
                });
        cerr << sl << '\n';
        for (int i : pot) {
            cerr << "  " << i;
        }
        cerr << '\n';
        {
            int lo = -1, hi = pot.size() - 1, mid;
            while (lo < hi) {
                w = vi(m, 0);
                int mid = lo + hi == -1 ? -1 : lo + hi >> 1;
                REP (i, mid + 1, pot.size()) {
                    w[p[pot[i]].SE] = 1;
                }
                REP (i, 0, m) {
                    if (back[i]) {
                        w[i] = 1;
                    }
                }
                cerr << lo << ' ' << hi << ' ' << mid << '\n';
                REP (i, 0, m) {
                    cerr << "   " << w[i];
                }
                cerr << '\n';
                ll toll = ask(w);
                if (toll == itoll) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }
            if (hi == -1) {
                s = sl;
            } else {
                cerr << "   !" << p[pot[hi]].FI << '\n';
                s = eg[p[pot[hi]].SE].FI;
            }
            cerr << ' ' << hi << ' ' << s << '\n';
        }
        assert(s != -1);
        swap(s, t);
        swap(sl, tl);
    }
    answer(s, t);
    cerr << s << ' ' << t << '\n';
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:65:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |             mid = lo + hi >> 1;
      |                   ~~~^~~~
highway.cpp:132:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |                 int mid = lo + hi == -1 ? -1 : lo + hi >> 1;
      |                                                ~~~^~~~
highway.cpp:14:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
  133 |                 REP (i, mid + 1, pot.size()) {
      |                      ~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:133:17: note: in expansion of macro 'REP'
  133 |                 REP (i, mid + 1, pot.size()) {
      |                 ^~~
highway.cpp:129:47: warning: unused variable 'mid' [-Wunused-variable]
  129 |             int lo = -1, hi = pot.size() - 1, mid;
      |                                               ^~~

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