P13614 [IOI 2018] highway 高速公路收费

· · 题解

很牛的题。

思路：

显然你可以将所有边赋值为 A 然后得到 S, T 之间的最短路 k A，那么考虑找到最短路上的一条边，容易想到依次赋值边权为 B，某个时刻 S, T 最短路变大了，那么最后赋值的那条边就在它们的最短路上。

依次赋值判断太慢了，显然满足单调性，可以二分边集前缀去找，要 \log m 次去找；设找到的边是 (x, y)，那么可以将所有点分为两类 A, B，到 x 更近和到 y 更近。

可以证明 S, T 必然一个在 A 一个在 B，可以反证法，若都在 A，那么 \operatorname{dis}(S, x) + w(x, y) + \operatorname{dis}(y, T) > \operatorname{dis}(S, x) + \operatorname{dis}(x, T)，于是存在不经过 (x, y) 的更短路，矛盾。

于是对于左右两个部分，分别建出以 x, y 为根的 bfs 树。

先求在左边的起点，右边类似，容易想到二分一个 bfs 序的前缀，将这个前缀上的点到上一层的边赋值为 A，其它在左边的边赋值为 B（注意还有左边到右边的所有边也要是 B，我因为这个调了好久），然后外面的点都赋值为 A；此时如果 S \to T 最短路等于 kA，即不变时，说明 S 一定在赋值为 A 的这个前缀中，于是也可以二分找到。

于是询问次数是 \log m + \log x + \log y \le \log m + 2 \log n (x + y = n)，是卡不满的，可以通过。

思路：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define lowbit(x) x & (-x)
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
//void answer(int s, int t){
//  printf("!ans %d %d\n", s, t);
//}
//long long ask(const vector<int> &w){
//  for(int i = 0; i < (int)w.size(); ++i)
//    putchar(w[i] + '0');
//  putchar('\n');
//  return read();
//}
ll ask(const vector<int> &w);
void answer(int s, int t);
const int N = 1.3e5 + 10;
struct edge{
    int u, v;
}e[N];
int n, m, a, b, edg, cnt;
int id[N], now[N], dep[N];
bool used[N];
ll dis;
vector<int> vis, fid[N];
vector<pair<int, int>> E[N];
inline void get(int x, int y){
    id[x] = 1, id[y] = 2;
    queue<int> q;
    q.push(x);
    q.push(y);
    used[x] = used[y] = 1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(auto t : E[u]){
            int v = t.fi;
            if(!used[v]){
                used[v] = 1;
                id[v] = id[u];
                q.push(v);
            }
        }
    }
}
inline int bfs(int u, int x){
//  cerr << "id: " << x << '\n';
    for(int i = 1; i <= n; ++i)
        fid[i].clear(), dep[i] = 1e9;
    for(int i = 0; i < m; ++i)
        vis[i] = 0;
    cnt = 0;
    queue<int> q;
    dep[u] = 0;
    q.push(u);
    while(!q.empty()){
        int u = q.front();
        q.pop();
//      cerr << "node: " << u << '\n';
        now[++cnt] = u;
        for(auto t : E[u]){
            int v = t.fi, w = t.se;
            if(id[v] == x){
                if(dep[v] > dep[u] + 1){
                    dep[v] = dep[u] + 1;
                    q.push(v);
                }
                if(dep[v] >= dep[u])
                  fid[v].push_back(w);
            }
        }
    }
    for(auto i = 1; i <= cnt; ++i)
      for(auto t : E[now[i]])
        if(id[t.fi] != x && t.se != edg)
          vis[t.se] = 1;
//  cerr << '\n';
    for(int i = 2; i <= cnt; ++i)
      for(auto v : fid[now[i]])
        vis[v] = 1;
//  cerr << '\n';
    int l = 1, r = cnt, pos = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        for(int i = 2; i <= mid; ++i)
            for(auto v : fid[now[i]])
                vis[v] = 0;
        if(ask(vis) == dis){
            pos = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
        for(int i = 2; i <= mid; ++i)
            for(auto v : fid[now[i]])
                vis[v] = 1; 
    }
    return now[pos];
}
inline void solve(){
    for(int i = 0; i < m; ++i)
        vis.push_back(0);
    dis = ask(vis);
    int l = 1, r = m, pos = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        for(int i = 0; i < mid; ++i)
            vis[i] = 1;
        if(ask(vis) != dis){
            pos = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
        for(int i = 0; i < mid; ++i)
            vis[i] = 0;     
    }
    int x = e[pos].u, y = e[pos].v;
    edg = pos - 1;
//  cerr << edg << '\n';
    get(x, y);
//  cerr << "edge: " << x << ' ' << y << '\n';
    int s = bfs(x, 1);
    int t = bfs(y, 2);
    answer(s - 1, t - 1);
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
    n = N, a = A, b = B, m = U.size();
    for(int i = 0; i < m; ++i){
        ++U[i], ++V[i];
        e[i + 1] = {U[i], V[i]};
        E[U[i]].push_back({V[i], i});
        E[V[i]].push_back({U[i], i});
    }
    solve();
}
//int main(){
//  int n = read(), m = read(), a = read(), b = read(), s = read(), t = read();
//  vector<int> U, V;
//  for(int u, v, i = 0; i < m; ++i){
//      u = read(), v = read();
//      U.push_back(u);
//      V.push_back(v);
//  }
//  find_pair(n, U, V, a, b);
//  return 0;
//}