Submission #1131813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131813		tredsused70	Evacuation plan (IZhO18_plan)	C++20	100 / 100	357 ms	44712 KiB

plan

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
//#pragma GCC optimize("trapv")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define mpr make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int nmax = 100011, mod = 1000000007, inf = 2000010000, key = 200003, lg = 20, block = 300;
const ll infll = 4000000000000000000;
const ld eps = 1e-9;

int dist[nmax], color[nmax], used[nmax] = {0};
vector<array<int, 2>> graf[nmax], tree[nmax];

void dickstra(int n) {
    set<array<int, 2>> st;
    for(int i = 1; i <= n; i++) {
        if(dist[i] == 0)
            st.insert({0, i});
    }
    while(!st.empty()) {
        auto cur = *st.begin();
        st.erase(st.begin());
        for(auto i : graf[cur[1]]) {
            if(dist[i[0]] > cur[0] + i[1]) {
                st.erase({dist[i[0]], i[0]});
                dist[i[0]] = cur[0] + i[1];
                st.insert({dist[i[0]], i[0]});
            }
        }
    }
    return ;
}

int prd[nmax] = {0};

int fpr(int u) {
    return prd[u] == 0 ? u : prd[u] = fpr(prd[u]);
}

bool unite(int u, int v) {
    u = fpr(u);
    v = fpr(v);
    if(u == v)
        return 0;
    prd[v] = u;
    return 1;
}

int d[nmax];
array<int, 2> jumps[lg][nmax];

void dfs(int v, int pr = 0) {
    for(auto i : tree[v]) {
        if(i[0] == pr)
            jumps[0][v] = {pr, i[1]};
        else {
            d[i[0]] = d[v] + 1;
            dfs(i[0], v);
        }
    }
    return ;
}

void precompute(int n) {
    d[0] = 0;
    jumps[0][1] = {0, 0};
    dfs(1);
    for(int i = 1; i < lg; i++) {
        for(int j = 1; j <= n; j++) {
            jumps[i][j] = jumps[i - 1][jumps[i - 1][j][0]];
            jumps[i][j][1] = min(jumps[i][j][1], jumps[i - 1][j][1]);
        }
    }
    return ;
}

int query(int u, int v) {
    if(d[u] > d[v])
        swap(u, v);
    int ans = inf;
    //cout << u << " " << v << " u v\n";
    //cout << d[u] << " " << d[v] << " depths\n";
    for(int i = lg - 1; i >= 0; i--) {
        if(d[v] - (1 << i) >= d[u]) {
            //cout << i << " " << jumps[i][v][1] << " i jump[1]\n";
            ans = min(ans, jumps[i][v][1]);
            v = jumps[i][v][0];
        }
    }
    for(int i = lg - 1; i >= 0; i--) {
        if(jumps[i][v][0] != jumps[i][u][0]) {
            ans = min(ans, jumps[i][v][1]);
            ans = min(ans, jumps[i][u][1]);
            v = jumps[i][v][0];
            u = jumps[i][u][0];
        }
    }
    if(u != v) {
        ans = min(ans, jumps[0][v][1]);
        ans = min(ans, jumps[0][u][1]);
    }
    return ans;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    fill(dist, dist + n + 1, inf);
    int u, v, w;
    for(int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        graf[u].pb({v, w});
        graf[v].pb({u, w});
    }
    int k;
    //cout << "Need k\n";
    cin >> k;
    for(int i = 0; i < k; i++) {
        cin >> u;
        dist[u] = 0;
    }
    dickstra(n);
    vector<array<int, 3>> edges;
    for(int i = 1; i <= n; i++)
        for(auto j : graf[i])
            if(i > j[0])
                edges.pb({min(dist[i], dist[j[0]]), i, j[0]});
    sort(all(edges));
    reverse(all(edges));
    for(int i = 0; i < m; i++) {
        if(unite(edges[i][1], edges[i][2])) {
            tree[edges[i][1]].pb({edges[i][2], edges[i][0]});
            tree[edges[i][2]].pb({edges[i][1], edges[i][0]});
        }
    }
    precompute(n);
    int q;
    cin >> q;
    for(int i = 0; i < q; i++) {
        cin >> u >> v;
        cout << query(u, v) << "\n";
    }
    return ;
}

int main()
{
    //freopen("wormsort.in","r",stdin);
    //freopen("wormsort.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    srand(8713);
    //init();
    int t = 1;
    //cin >> t;
    //int t_ = t;
    //t = rdi();
    while(t--) {
        //cout << "Case #" << t_ - t << ": ";
        solve();
    }
    //flush();
    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
*/

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