제출 #521779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521779		vonatlus	Evacuation plan (IZhO18_plan)	C++17	100 / 100	465 ms	50676 KiB

plan

/// adil sultanov | vonat1us 

#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:36777216")

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define sz(x) (int) x.size()
#define all(z) (z).begin(), (z).end()
 
using namespace std;

using ll = long long;
using pii = pair<int, int>;                                   

const int MOD = 1e9 + 7; 
const int INF = 1e9 + 1e2;
  
void fin() {
#ifdef AM
    freopen(".in", "r", stdin);
#endif        
}                   

const bool flag = 0;

const int N = 1e5+10;
const int K = 17;

vector<pii> adj[N];

int d[N];

void dijkstra(int n, int k) {
    for (int i = 0; i < n; ++i) d[i] = INF;
    priority_queue<pii> q;
    for (int i = 0; i < k; ++i) {
        int x;
        cin >> x, x--;
        q.push({0, x});
        d[x] = 0;
    }
    while (!q.empty()) {
        auto [w, x] = q.top();
        q.pop();
        if (d[x] != -w) {
            continue;
        }
        for (auto [to, we] : adj[x]) {
            if (d[to] > d[x]+we) {
                d[to] = d[x]+we;
                q.push({-d[to], to});
            }
        }
    }
}

int p[N], sz[N];

int fnd(int x) {
    if (x == p[x]) return x;
    return p[x] = fnd(p[x]);
}

bool unite(int u, int v) {
    u = fnd(u);
    v = fnd(v);
    if (u == v) return false;
    if (sz[u] > sz[v]) swap(u, v);
    p[u] = v;
    sz[v] += sz[u];
    return true;
}

int tin[N], tout[N], tmr;

int up[K][N], mn[K][N];

void dfs(int x = 0, int p = 0) {
    tin[x] = ++tmr;
    up[0][x] = p;
    for (int i = 1; i < K; ++i) {
        up[i][x] = up[i-1][up[i-1][x]];
        mn[i][x] = min(mn[i-1][x], mn[i-1][up[i-1][x]]);
    }
    for (auto [to, w] : adj[x]) {
        if (to != p) {
            mn[0][to] = w;
            dfs(to, x);
        }    
    }
    tout[x] = tmr;
}

bool upper(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int get(int s, int t) {
    int res = INF;
    for (int i = K-1; ~i; --i) {
        if (!upper(up[i][s], t)) {
            res = min(res, mn[i][s]);
            s = up[i][s];
        }
    }
    for (int i = K-1; ~i; --i) {
        if (!upper(up[i][t], s)) {
            res = min(res, mn[i][t]);
            t = up[i][t];
        }
    }
    if (upper(s, t)) {
        res = min(res, mn[0][t]);
    } else if (upper(t, s)) {
        res = min(res, mn[0][s]);
    } else {
        res = min(res, mn[0][t]);
        res = min(res, mn[0][s]);
    }
    return res;
}

void ma1n() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, pii>> e;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        e.pb({1, {u, v}});
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }    
    int k;
    cin >> k;
    dijkstra(n, k);
    for (int i = 0; i < n; ++i) {
        adj[i].clear();
    }
    for (auto& it : e) {
        it.x = min(d[it.y.x], d[it.y.y]);
    }
    sort(all(e));
    reverse(all(e));
    for (int i = 0; i < n; ++i) {
        p[i] = i, sz[i] = 1;
    }
    for (auto it : e) {
        auto [u, v] = it.y;
        if (unite(u, v)) {
            adj[u].pb({v, it.x});
            adj[v].pb({u, it.x});
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < K; ++j) {
            mn[j][i] = INF;
        }
    }
    dfs();
    int q;
    cin >> q;
    for (int s, t; q--;) {
        cin >> s >> t;
        s--, t--;
        cout << get(s, t) << "\n";
    }
} 

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr), fin();
    int ts = 1;
    if (flag) {
        cin >> ts;
    }
    while (ts--) {
        ma1n(); 
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46