Submission #511372

#	Time	Username	Problem	Language	Result	Execution time	Memory
511372		inventiontime	Evacuation plan (IZhO18_plan)	C++17	0 / 100	4064 ms	69488 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;

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;

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() {

    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;  
        }
    }

}

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;

}

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