Submission #1128981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128981		dwuy	Evacuation plan (IZhO18_plan)	C++20	100 / 100	378 ms	62588 KiB

plan

/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "IZhO18_plan"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;

struct DSU{
    vector<int> e;
    DSU(int n = 0) : e(n + 5, - 1) {}

    int fp(int u){
        return e[u] < 0? u : e[u] = fp(e[u]);
    }

    bool unon(int u, int v){
        u = fp(u);
        v = fp(v);
        if(u == v) return 0;
        if(e[u] > e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
        return 1;
    }
};

int n, m, k, q;
int P[MX], d[MX];
int h[MX];
int p[MX][17];
int f[MX][17];
vector<pii> G[MX];
vector<int> T[MX];

void dijkstra(){
    memset(d, 0x3f, sizeof d);
    priority_queue<pii, vector<pii>, greater<pii>> Q;
    for(int i=1; i<=k; i++){
        int u = P[i];
        d[u] = 0;
        Q.push({0, u});
    }
    while(Q.size()){
        int du, u;
        tie(du, u) = Q.top();
        Q.pop();
        if(du != d[u]) continue;
        for(pii e: G[u]){
            int v, c;
            tie(v, c) = e;
            if(d[v] > du + c){
                d[v] = du + c;
                Q.push({d[v], v});
            }
        }
    }
}

bool comp(const int &u, const int &v){
    return d[u] > d[v];
}

void dfs(int u){
    h[u] = h[p[u][0]] + 1;
    for(int i=1; i<=16; i++){
        p[u][i] = p[p[u][i-1]][i-1];
        f[u][i] = min(f[u][i-1], f[p[u][i-1]][i-1]);
    }
    for(int v: T[u]) if(v != p[u][0]){
        p[v][0] = u;
        f[v][0] = min(d[u], d[v]);
        dfs(v);
    }
}

void build(){
    vector<int> vt(n);
    for(int i=1; i<=n; i++) vt[i - 1] = i;
    sort(vt.begin(), vt.end(), comp);
    bitset<MX> active = 0;
    DSU dsu(n);
    for(int u: vt){
        active[u] = 1;
        for(pii e: G[u]) if(active[e.fi]){
            int v = e.fi;
            if(dsu.unon(u, v)){
                T[u].push_back(v);
                T[v].push_back(u);
            }
        }
    }
    dfs(1);
}

int get(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int res = 1e18;
    for(int i=16; i>=0; i--) if(h[p[u][i]] >= h[v]){
        res = min(res, f[u][i]);
        u = p[u][i];
    }
    if(u == v) return res;
    for(int i=16; i>=0; i--) if(p[u][i] != p[v][i]){
        res = min({res, f[u][i], f[v][i]});
        u = p[u][i];
        v = p[v][i];
    }
    res = min({res, f[u][0], f[v][0]});
    return res;
}

int32_t main(){
    fastIO;
    //file(TASK);

    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    cin >> k;
    for(int i=1; i<=k; i++) cin >> P[i];
    dijkstra();
    build();
    cin >> q;
    while(q--){
        int u, v;
        cin >> u >> v;
        cout << get(u, v) << endl;
    }

    return 0;
}

/**

 9 12
 1 9 4
 1 2 5
 2 3 7
 2 4 3
 4 3 6
 3 6 4
 8 7 10
 6 7 5
 5 8 1
 9 5 7
 5 4 12
 6 8 2
 2
 4 7
 5
 1 6
 5 3
 4 8
 5 8
 1 5


 5
 5
 0
 7
 8


**/

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