Submission #1173710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173710		qrn	Evacuation plan (IZhO18_plan)	C++20	100 / 100	435 ms	101028 KiB

plan

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

// template<class T>
// using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 31;
const intt inf = 1e18;
const intt mxN = 2e5 + 5;
const intt L = 18;

vector<vector<pair<intt,intt>>> graph, tgraph;
vector<vector<intt>> up, mini;
vector<intt> npp(mxN), used(mxN), dis(mxN), in(mxN), out(mxN), depth(mxN);
intt n, m, timer;

void dfs(intt node, intt parent) {
    in[node] = timer++;
    up[0][node] = parent;
    for(intt i = 1; i <= L; i++) {
        up[i][node] = up[i-1][up[i-1][node]];
    }
    
    for(auto u : tgraph[node]) {
        if(u.fi != parent) {
            mini[0][u.fi] = u.se;
            depth[u.fi] = depth[node] + 1;
            dfs(u.fi, node);
        }
    }
    out[node] = timer++;
}

bool isata(intt a, intt b) {
    return in[a] <= in[b] && out[a] >= out[b];
}

intt lca(intt a, intt b) {
    if(isata(a,b)) return a;
    if(isata(b,a)) return b;
    
    for(intt i = L - 1; i >= 0; i--) {
        if(!isata(up[i][a], b)) {
            a = up[i][a];
        }
    }
    return up[0][a];
}


intt bl(intt node, intt k) {
    intt ret = inf;
    for(intt i = 0; i < L; i++) {
        if(((1 << i) & k)) {
            ret = min(ret, mini[i][node]);
            node = up[i][node];
        }
    }
    return ret;
}


void dijkstra() {
    for(intt i = 1; i <= n; i++) {
        dis[i] = inf;
    }
    
    priority_queue<pair<intt,intt>, vector<pair<intt,intt>>, greater<pair<intt,intt>>>pq;
    for(intt i = 1; i <= n; i++) {
        if(npp[i]) {
            dis[i] = 0;
            pq.push({dis[i], i});
            // cout << i << " ";
        }
    }
    // cout << endl;
    
    while(not pq.empty()) {
        intt d = pq.top().fi;
        intt cur = pq.top().se;
        pq.pop();
        for(auto u : graph[cur]) {
            if(dis[u.fi] > dis[cur] + u.se) {
                dis[u.fi] = dis[cur] + u.se;
                pq.push({dis[u.fi], u.fi});
            }
        }
    }
    
    // for(intt i = 1; i <= n; i++) dis[i]--;
}

struct DSU{
    vector<intt> parent, sze;
    DSU(intt n) {
        parent.resize(n + 1);
        sze.resize(n + 1);
        for(intt i = 1; i <= n; i++){
            parent[i] = i;
            sze[i] = 1;
        }
    }
    
    intt root(intt x) {
        if(parent[x] == x) return x;
        else return parent[x] = root(parent[x]);
    }
    
    void unite(intt a, intt b) {
        a = root(a);
        b = root(b);
        if(a == b) return;
        
        if(sze[a] < sze[b]) swap(a, b);
        parent[b] = a;
        sze[a] += sze[b];
    }
};

vector<array<intt,3>> edges;

bool cmp(array<intt,3> &a, array<intt,3> &b) {
    return a[2] > b[2];
}

intt W = 0;
void kruskal() {
    DSU dsu(n + 1);
    sort(ALL(edges), cmp);
    
    for(auto e : edges) {
        if(dsu.root(e[0]) != dsu.root(e[1])) {
            dsu.unite(e[0], e[1]);
            tgraph[e[0]].pb({e[1], e[2]});
            tgraph[e[1]].pb({e[0], e[2]});
            W += e[2];
        }
    }
}



void solve() {
    cin >> n >> m;
    graph.assign(n + 1, vector<pair<intt,intt>>{});
    tgraph.assign(n + 1, vector<pair<intt,intt>>{});
    up.assign(L + 1, vector<intt>(n + 1, 0ll));
    mini.assign(L + 1, vector<intt>(n + 1, inf));
    
    for(intt i = 1; i <= m; i++) {
        intt a, b, w;
        cin >> a >> b >> w;
        graph[a].pb({b, w});
        graph[b].pb({a, w});
    }
    
    intt k;
    cin >> k;
    for(intt i = 0; i < k; i++){
        intt x; cin >> x;
        npp[x] = 1;
    }
    dijkstra();
    
    for(intt i = 1; i <= n; i++) {
        for(auto u : graph[i]) {
            intt w = min(dis[i], dis[u.fi]);
            edges.pb({u.fi, i, w});
        }
    }
    kruskal();
    
    dfs(1, 1);
    
    // for(intt i = 1; i <= n; i++){
    //     if(tgraph[i].empty()) {
    //         continue;
    //     }
        
    //     for(auto u : tgraph[i]) {
    //         cout << i << " " << u.fi << " " << u.se << endl;
    //     }
    // }
    // cout << W << endl;
  
    for(intt i = 1; i <= L; i++) {
        for(intt node = 1; node <= n; node++){
            mini[i][node] = min(mini[i-1][node], mini[i-1][up[i-1][node]]);
        }
    }
    
    // for(intt i = 1; i <= n; i++) {
    //     cout << depth[i] << " ";
    // }
    // cout << endl;
    
    intt q;
    cin >> q;
    while(q--) {
        intt a, b;
        cin >> a >> b;
        intt l = lca(a, b);
        intt solans = bl(a, depth[a] - depth[l]);
        intt sagans = bl(b, depth[b] - depth[l]);
        cout << min(solans, sagans) << endl;
        // cout << min(solans, sagans) << " " << l << " " << mini[0][3] << " " << solans << " " << sagans << " " << depth[l] - depth[a] << endl;;
    }
}

signed main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

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