Submission #1326832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326832		husseinjuanda	Evacuation plan (IZhO18_plan)	C++20	0 / 100	144 ms	25808 KiB

plan

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

vector<int> ans;
vector<int> par;
vector<vector<int>> isi;
vector<vector<pair<int, int>>> que;

int fpar(int k){
    if(par[k] == k) return k;
    par[k] = fpar(par[k]);
    return par[k];
}

int cursz = 0;

void merge(int k, int f){
    k = fpar(k);
    f = fpar(f);
    //k itu yg lebih kecil sizenya
    if(isi[k].size() > isi[f].size()){
        swap(k, f);
    }
    for(auto y : isi[k]){
        for(auto j : que[y]){
            int fp = fpar(j.first);
            if(fp == f){
                ans[j.second] = max(ans[j.second], cursz);
            }
        }
        isi[f].push_back(y);
    }
    par[k] = f;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    isi.resize(n+1);
    par.resize(n+1);
    for(int i = 1; i <= n; i++){
        par[i] = i;
        isi[i] = {i};
    }
    vector<vector<pair<int, int>>> g(n+1);
    for(int i = 0; i < m; i++){
        int a, b, w; cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    int c; cin >> c;
    multiset<pair<int, int>> s;
    vector<bool> d(n+1);
    vector<int> dis(n+1, 1e18);
    for(int i = 0; i < c; i++){
        int h; cin >> h;
        s.insert({0, h});
        dis[h] = 0;
    }
    while(s.size() > 0){
        auto [time, k] = *s.begin();
        s.erase(s.begin());
        if(d[k]) continue;
        d[k] = true;
        for(auto[a, b] : g[k]){
            if(d[a]) continue;
            if(dis[a] > time + b){
                dis[a] = time+b;
                s.insert({dis[a], a});
            }
        }
    }
    // cout << "CHECK" << endl;
    // for(int y = 1; y <= n; y++){
    //     cout << dis[y] << endl;
    // }
    vector<int> srt = dis;
    sort(srt.begin(), srt.end());
    srt.erase(unique(srt.begin(), srt.end()), srt.end());
    reverse(srt.begin(), srt.end());
    map<int, vector<int>> mp;
    for(int i = 1; i <= n; i++){
        mp[dis[i]].push_back(i);
    }
    int q; cin >> q;
    que.resize(n+1);
    for(int i = 0; i < q; i++){
        int a, b; cin >> a >> b;
        que[a].push_back({b, i});
        que[b].push_back({a, i});
    }
    ans.resize(q);
    for(auto i : srt){
        cursz = i;
        for(auto y : mp[i]){
            for(int z = 0; z < g[y].size(); z++){
                if(dis[g[y][z].first] >= cursz){
                    merge(g[y][z].first, y);
                }
            }
        }
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

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