제출 #556335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556335		maomao90	통행료 (IOI18_highway)	C++17	0 / 100	20 ms	9844 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;
int dis[2][MAXN];

ii p[MAXN];
int lvl[MAXN];
int vis[MAXN];
bool back[MAXN];
void dfs(int u) {
    vis[u] = 1;
    for (auto [v, i] : adj[u]) {
        if (v == p[u].FI) continue;
        if (vis[v] == 1) {
            back[i] = 1;
        }
        if (vis[v]) continue;
        if (dis[0][v] >= dis[1][v]) continue;
        p[v] = {u, i};
        lvl[v] = lvl[u] + 1;
        dfs(v);
    }
    vis[u] = 2;
}

void bfs(int s, int z) {
    queue<int> q;
    REP (i, 0, n) {
        dis[z][i] = INF;
    }
    q.push(s);
    dis[z][s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, i] : adj[u]) {
            if (mnto(dis[z][v], dis[z][u] + 1)) {
                q.push(v);
            }
        }
    }
}

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);
    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];
    }
    assert(sl != -1);
    cerr << sl << ' ' << tl << '\n';
    bfs(sl, 0); bfs(tl, 1);
    int s = -1, t = -1;
    REP (z, 0, 2) {
        dfs(sl);
        REP (i, 0, m) {
            if (lvl[eg[i].FI] < lvl[eg[i].SE]) {
                swap(eg[i].FI, eg[i].SE);
            }
        }
        vi pot;
        REP (i, 0, n) {
            if (i == sl) continue;
            if (dis[0][i] < dis[1][i]) {
                pot.pb(i);
            }
        }
        sort(ALL(pot), [&] (int l, int r) {
                return lvl[l] < lvl[r];
                });
        {
            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;
                }
            }
            cerr << ' ' << hi << '\n';
            if (hi == -1) {
                s = sl;
            } else {
                s = eg[pot[hi]].FI;
            }
        }
        assert(s != -1);
        memset(lvl, 0, sizeof lvl);
        memset(back, 0, sizeof back);
        memset(vis, 0, sizeof vis);
        swap(s, t);
        swap(sl, tl);
        swap(dis[0], dis[1]);
    }
    answer(s, t);
    cerr << s << ' ' << t << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:97:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |             mid = lo + hi >> 1;
      |                   ~~~^~~~
highway.cpp:136:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  136 |                 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++)
......
  137 |                 REP (i, mid + 1, pot.size()) {
      |                      ~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:137:17: note: in expansion of macro 'REP'
  137 |                 REP (i, mid + 1, pot.size()) {
      |                 ^~~
highway.cpp:133:47: warning: unused variable 'mid' [-Wunused-variable]
  133 |             int lo = -1, hi = pot.size() - 1, mid;
      |                                               ^~~

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