Submission #1161851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161851		MPG	Evacuation plan (IZhO18_plan)	C++20	100 / 100	1623 ms	74864 KiB

plan

//#pragma GCC optomize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse4.1,sse4.2") 



#include <bits/stdc++.h>
using namespace std;
typedef long long       ll;
#define     max_heap priority_queue<pair <ll, pair <ll, ll>>>
#define     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
#define     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define     filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout); 
#define     endl '\n'
#define     md(a) (a % mod + mod) % mod
#define     pb push_back
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//cout << setprecision(5) << fixed << f;
//hash prime = 769


ll const maxn = 2e5 + 123;
ll const inf = 2e18;
ll const loG = 23;
ll const mod = 1e9 + 7;
//ll const mod = 998244353;
ll const sq = 500;
ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}




ll n, m, k, q, dis[maxn], par[maxn], sz[maxn];
pair <ll, ll> baz[maxn], man[maxn];
vector <pair <ll, ll>> g[maxn], yal, ras, pors;
vector <pair <pair <ll, ll>, ll>> chi;
vector <ll> bad, gg[maxn];
bool mark[maxn];


ll get(ll v){
    if (par[v] == v)
        return v;
    return get(par[v]);
}

void merge(ll v, ll u){
    v = get(v), u = get(u);
    if (v == u){
        chi.pb({{v, u}, 0});
        return;
    }
    if (sz[v] <= sz[u])
        swap(v, u);
    sz[v] += sz[u];
    par[u] = v;
    chi.pb({{v, u}, 1});
}

void roll(){
    if (chi.back().second){
        ll v = chi.back().first.first, u = chi.back().first.second;
        sz[v] -= sz[u];
        par[u] = u;
    }
    chi.pop_back();
}





void djk(){
    for (int i = 1; i < n + 1; i++)
        dis[i] = inf;
    min_heap qu;
    for (ll x : bad){
        dis[x] = 0;
        qu.push({0, x});
    }
    while (qu.size()){
        ll v = qu.top().second; qu.pop();
        if (mark[v])
            continue;
        mark[v] = 1;
        for (auto u : g[v]){
            if (!mark[u.first] && dis[u.first] > dis[v] + u.second){
                dis[u.first] = dis[v] + u.second;
                qu.push({dis[u.first], u.first});
            }
        }
    }
}







void Solve(){

cin >> n >> m;
for (int i = 1; i < m + 1; i++){
    ll a, b, c; cin >> a >> b >> c;
    yal.pb({a, b});
    g[a].pb({b, c});
    g[b].pb({a, c});
}
cin >> k;
for (int i = 1; i < k + 1; i++){
    ll x; cin >> x;
    bad.pb(x);
}
djk();


// for (int i = 1; i < n + 1; i++){
//     cout << i << ' ' << dis[i] << endl;
// }



cin >> q;
for (int i = 1; i < q + 1; i++){
    cin >> man[i].first >> man[i].second;
    baz[i].first = 0, baz[i].second = mod;
}
for (int i = 1; i < n + 1; i++)
    ras.pb({dis[i], -i});
sort(ras.begin(), ras.end()); reverse(ras.begin(), ras.end());
for (auto p : yal){
    ll a = p.first, b = p.second;
    if (dis[a] > dis[b])
        gg[b].pb(a);
    else if (dis[a] < dis[b])
        gg[a].pb(b);
    else{
        gg[max(a, b)].pb(min(a, b));
    }
}
// for (auto p : ras)
//     cout << p.first << ' ' << -p.second << ' ' << dis[-p.second] << endl;
bool ok = 1;
while (ok){
    ok = 0;
    chi.clear();
    pors.clear();
    for (int i = 1; i < n + 1; i++){
        par[i] = i;
        sz[i] = 1;
    }
    for (auto v : ras){
        ll a = -v.second;
        for (auto b : gg[a]){
            merge(a, b);
        }
    }
    for (int i = 1; i < q + 1; i++){
        ll l = baz[i].first, r = baz[i].second;
        if (r - l > 1){
            ll mid = (l + r) / 2;
            ok = 1;
            pors.pb({mid, i});
        }
    }
    sort(pors.begin(), pors.end());
    ll ind = ras.size() - 1;
    for (auto p : pors){
        ll id = p.second, d = p.first;
        //cout << "porsing " << d << endl;
        while ((ind > -1) && (ras[ind].first < d)){
            ll v = -ras[ind].second;
            //cout << "pak " << v << endl;
            for (int tmp = 0; tmp < gg[v].size(); tmp++)
                roll();
            ind--;
        }
        ll a = man[id].first, b = man[id].second;
        a = get(a), b = get(b);
        if (a == b){
            baz[id].first = d;
        }
        else
            baz[id].second = d;
    }
}
for (int i = 1; i < q + 1; i++)
    cout << baz[i].first << endl;



}





int main(){
//sariE;// filE;



int test = 1;
//cin >> test;
while (test--) Solve();
return 0;
}

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