백준13208 승현이와 승현이

작성일 | In

문제 링크

  • http://icpc.me/13208

사용 알고리즘

  • MST
  • LCA
  • Sparse Table

시간복잡도

  • $O(M \log M + Q \log N)$

풀이

13과 16이 각각 $u, v$에 있는 상태를 $(u, v)$로 정의하고, 간선을 적절히 만들어서 새로운 그래프를 만들어줍시다. $(S, E)$에서 $(E, S)$로 갈 때 지나가는 가중치의 최댓값을 최소화하는 문제입니다.

MST를 구하고 경로 최댓값 쿼리를 날리면 되는 간단한 문제입니다.
MST 간선만 뽑아놓고 PBS를 돌려도 되고, MST를 만든 뒤 Sparse Table이나 HLD로 최댓값 쿼리를 날려도 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

struct Edge{
    int s, e, x;
    Edge(int s, int e, int x) : s(s), e(e), x(x) {}
    bool operator < (const Edge &t) const {
        return tie(x, s, e) < tie(t.x, t.s, t.e);
    }
};

int pp[505050];
void init(){ iota(pp, pp + 505050, 0); }
int find(int v){ return v == pp[v] ? v : pp[v] = find(pp[v]); }
bool merge(int u, int v){ u = find(u); v = find(v); if(u == v) return 0; pp[u] = v; return 1; }
inline int id(int u, int v){ return u * 500 + v; }

int n, m, q; ll cst[555], c[505050];
vector<int> inp[555];
vector<Edge> edge;

vector<p> g[505050];
int par[22][505050], dep[505050], mx[22][505050];
void dfs(int v, int b){
    for(auto i : g[v]) if(i.x != b) {
        par[0][i.x] = v; mx[0][i.x] = i.y;
        dep[i.x] = dep[v] + 1;
        dfs(i.x, v);
    }
}
int lca(int u, int v){
    int ret = 0;
    if(dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for(int i=0; diff; i++){
        if(diff & 1) ret = max(ret, mx[i][u]), u = par[i][u];
        diff >>= 1;
    }
    if(u == v) return ret;
    for(int i=21; ~i; i--){
        if(par[i][u] != par[i][v]){
            ret = max({ret, mx[i][u], mx[i][v]});
            u = par[i][u]; v = par[i][v];
        }
        ret = max({ret, mx[0][u], mx[0][v]});
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m; for(int i=1; i<=n; i++) cin >> cst[i];
    for(int i=1; i<=m; i++){
        int s, e; cin >> s >> e;
        inp[s].push_back(e); inp[e].push_back(s);
    }
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) c[id(i, j)] = cst[i] * cst[j];
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) {
        for(auto k : inp[i]) edge.emplace_back(id(i, j), id(k, j), max(c[id(i, j)], c[id(k, j)]));
        for(auto k : inp[j]) edge.emplace_back(id(i, j), id(i, k), max(c[id(i, j)], c[id(i, k)]));
    }
    sort(all(edge));

    init();
    for(auto i : edge){
        if(merge(i.s, i.e)){
            g[i.s].emplace_back(i.e, i.x);
            g[i.e].emplace_back(i.s, i.x);
        }
    }
    dfs(id(1, 1), -1);
    for(int i=1; i<22; i++) for(int j=1; j<505050; j++){
        par[i][j] = par[i-1][par[i-1][j]];
        mx[i][j] = max({mx[i][j], mx[i-1][j], mx[i-1][par[i-1][j]]});
    }

    cin >> q;
    for(int i=0; i<q; i++){
        int s, e; cin >> s >> e;
        cout << lca(id(s, e), id(e, s)) << "\n";
    }
}