Submission #492409

#	Time	Username	Problem	Language	Result	Execution time	Memory
492409		baokhue232005	Evacuation plan (IZhO18_plan)	C++14	0 / 100	203 ms	38548 KiB

plan

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

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

#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 300005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k;

vector<ii> vc[maxN];
int m;
int dist[maxN];

int par[maxN];
set<int> st[maxN];
int ans[maxN];

int find(int i){
    if(par[i] <= 0) return i;
    return par[i] = find(par[i]);
}

void unite(int root, int node){
    root = find(root); node = find(node);
    int v1 = -par[root];
    int v2 = -par[node];
    if(root == node || v1 > v2) return;
    par[node] = root;
    if(st[node].size() > st[root].size()) swap(st[node], st[root]);
    for(int cc : st[node]){
        if(st[root].find(cc) == st[root].end()) st[root].insert(cc);
        else{
            st[root].erase(cc); ans[cc] = v1;
        }
    }
}

signed main(){
    // freopen(".inp", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for1(i, 1, m){
        cin >> x >> y >> z;
        vc[x].pb(ii(z, y));
        vc[y].pb(ii(z, x));
    }
    cin >> k;
    memset(dist, 126, sizeof(dist));
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    while(k--){
        cin >> x; dist[x] = 0; pq.push(ii(0, x));
    }
    while(!pq.empty()){
        ii pr = pq.top(); pq.pop();
        int node = pr.se;
        if(pr.fi == dist[node]){
            for(ii cc : vc[node]){
                z = cc.fi + pr.fi;
                if(dist[cc.se] > z){
                    dist[cc.se] = z;
                    pq.push(ii(z, cc.se));
                }
            }
        }
    }
    vector<ii> pichim;
    for1(i, 1, n){
        par[i] = -dist[i];
        cout << dist[i] << " ";
        pichim.pb(ii(dist[i], i));
    }
    cout << endl;
    int o; cin >> o; for1(i, 1, o){
        cin >> x >> y;
        st[x].insert(i);
        st[y].insert(i);
    }
    sort(all(pichim), greater<ii>());
    for(ii clclc : pichim){
        int root = clclc.se;
        for(ii pr : vc[root]){
            unite(root, pr.se);
        }
    }
    for1(i, 1, o){
        cout << ans[i] << endl;
    }
}

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