Submission #173856

#	Time	Username	Problem	Language	Result	Execution time	Memory
173856		VEGAnn	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1802 ms	40908 KiB

plan

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int, int>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
using namespace std;
const int oo = 2e9;
const int N = 100100;
vector<pii> g[N];
vector<int> qr[N];
set<pii> st;
int n, m, U[N], V[N], L[N], R[N], mid[N], pr[N], nm[N], dst[N], k, q;
bool mrk[N];

bool cmp(int x, int y){
    return dst[x] > dst[y];
}

int get(int x) { return (pr[x] == x ? x : pr[x] = get(pr[x])); }

void link(int x, int y){
    x = get(x); y = get(y);
    if (x != y)
        pr[x] = y;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int x, y, w; cin >> x >> y >> w;
        x--; y--;
        g[x].PB(MP(y, w));
        g[y].PB(MP(x, w));
    }

    fill(dst, dst + n, oo);

    cin >> k;
    for (int i = 0; i < k; i++){
        int x; cin >> x;
        x--;
        dst[x] = 0;
        st.insert(MP(0, x));
    }

    while (sz(st)){
        int v = (*st.begin()).sd;
        st.erase(st.begin());

        for (pii u : g[v])
            if (dst[u.ft] > dst[v] + u.sd){
                st.erase(MP(dst[u.ft], u.ft));
                dst[u.ft] = dst[v] + u.sd;
                st.insert(MP(dst[u.ft], u.ft));
            }
    }

    for (int i = 0; i < n; i++)
        nm[i] = i;
    sort(nm, nm + n, cmp);

    cin >> q;
    for (int i = 0; i < q; i++){
        cin >> U[i] >> V[i];
        U[i]--; V[i]--;
        L[i] = 0; R[i] = n - 1;
    }

    for (bool was = 1; was;){
        was = 0;
        for (int i = 0; i < q; i++)
            if (L[i] < R[i]){
                mid[i] = (L[i] + R[i]) >> 1;
                qr[mid[i]].PB(i);
                was = 1;
            }

        for (int i = 0; i < n; i++){
            mrk[i] = 0;
            pr[i] = i;
        }

        for (int it = 0; it < n; it++){
            int v = nm[it];
            mrk[v] = 1;

            for (pii u : g[v])
                if (mrk[u.ft])
                    link(v, u.ft);

            if (sz(qr[it])){
                for (int nm : qr[it])
                    if (get(U[nm]) == get(V[nm]))
                        R[nm] = mid[nm];
                    else L[nm] = mid[nm] + 1;

                qr[it].clear();
            }
        }
    }

    for (int i = 0; i < q; i++)
        cout << dst[nm[L[i]]] << '\n';

    return 0;
}

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