Submission #511390

#	Time	Username	Problem	Language	Result	Execution time	Memory
511390		inventiontime	Evacuation plan (IZhO18_plan)	C++17	0 / 100	162 ms	46604 KiB

plan

#include<bits/stdc++.h>
using namespace std;

#define int ll
//#define endl '\n'

#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pb push_back
#define re resize
#define all(x) (x).begin(), (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)
#define print(x) cout << #x << ": " << x << endl

#define maxn ((int) 1e5 + 5)
#define inf ((int) 1e17)

typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;
typedef priority_queue<ii> pq;
typedef priority_queue<ti> pqti;

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a,b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a,b); return B; }

int n, m, k, q;
vii adj[maxn];
int danger[maxn];
int npp[maxn];

vi tadj[maxn];

int tin[maxn];
int tout[maxn];
int par[maxn][32];
int par_min[maxn][32];

int cnt;

vi dsu;

void init_dsu(int n) {
    dsu.resize(n);
    loop(i, n+1) { dsu[i] = -1; }
}

int find(int v) {
    while(dsu[v] >= 0) v = dsu[v];
    return v;
}

bool merge(int u, int v) {
    u = find(u);
    v = find(v);
    if(u == v) return false;
    if(-dsu[u] < -dsu[v]) swap(u, v);
    dsu[u] += dsu[v];
    dsu[v] = u;   
    return true;
}

void dfs(int v, int p)
{
    tin[v] = ++cnt;
    par[v][0] = p;
    par_min[v][0] = danger[v];

    for (int u : tadj[v]) {
        if (u != p)
            dfs(u, v);
    }

    tout[v] = ++cnt;
}

bool ancestor(int anc, int v) {
    return tin[anc] <= tin[v] and tout[anc] >= tout[v];
}

void calc_danger() {

    loop1(i, n) danger[i] = inf;
    loop(i, k) adj[0].pb({npp[i], 0});

    pq nodes;
    danger[0] = 0;
    nodes.push({0, 0});
    while(!nodes.empty()) {
        auto [d, u] = nodes.top(); nodes.pop(); d *= -1;
        if(d != danger[u]) continue;
        for(auto [v, w] : adj[u])
            if(ckmin(danger[v], d+w))
                nodes.push({-danger[v], v});
    }

}

void calc_tree() {

    pqti edges;
    loop1(u, n) for(auto &[v, _] : adj[u])
        if(u > v) edges.push({min(danger[u], danger[v]), u, v});
    
    while(-dsu[find(1)] < n) {
        auto [w, u, v] = edges.top(); edges.pop();
        if(merge(u, v)) {
            tadj[u].pb(v);
            tadj[v].pb(u);
        } 
    }

}

void calc_lifting() {

    cnt = 0;
    dfs(1, 1);
    
    for(int i = 1; i <= 31; ++i) loop1(v, n) {
        par[v][i] = par[par[v][i-1]][i-1];
        par_min[v][i] = min(par_min[par[v][i-1]][i-1], par_min[v][i-1]);
    }

}

int query(int s, int t) {

    int anc;
    int res = min(danger[s], danger[t]);

    anc = s;
    for(int i = 31; i >= 0; i--) {
        while(!ancestor(par[anc][i], t)) {
            ckmin(res, par_min[anc][i]);
            anc = par[anc][i];
        }
    }

    if(!ancestor(anc, t))
        ckmin(res, par_min[anc][0]);
    
    anc = t;
    for(int i = 31; i >= 0; i--) {
        while(!ancestor(par[anc][i], s)) {
            ckmin(res, par_min[anc][i]);
            anc = par[anc][i];
        }
    }

    if(!ancestor(anc, s))
        ckmin(res, par_min[anc][0]);

    return res;

}

void solve() {
    
    cin >> n >> m;
    loop(i, m) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].pb({b, w});
        adj[b].pb({a, w});
    }

    cin >> k;
    loop(i, k) cin >> npp[i];

    calc_danger();
    calc_tree();
    calc_lifting();

    cin >> q;
    loop(idx, q) {
        int s, t;
        cin >> s >> t;
        cout << query(s, t) << endl;
    }

}

signed main(){

    fast_io;

    int t = 1; //cin >> t;
    while(t--)
        solve();

    //cout << flush;

    return 0;

}

/*
    pq nodes;
    bool vis[n+1] = {};
    loop1(i, n) nodes.push({danger[i], i});
    vis[nodes.top()[1]] = true;
    while(!nodes.empty()) {
        auto [w, u] = nodes.top(); nodes.pop();
        for(auto [v, _] : adj[u]) if(!vis[v]) {
            tadj[u].pb(v);
            tadj[v].pb(u);
            vis[v] = true;  
        }
    }
*/

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