Submission #466607

#	Time	Username	Problem	Language	Result	Execution time	Memory
466607		TeaTime	Evacuation plan (IZhO18_plan)	C++17	0 / 100	790 ms	23144 KiB

plan

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <cmath>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define int ll
typedef long long ll;
typedef long double ld;

const ll SZ = 1e5 + 100, LG = 20, INF = 1e9 * 1e9 + 100;

ll n, m, dsu[SZ];
ll k;
vector<ll> bad;
vector<vector<pair<ll, ll>>> gr;

struct qs {
    int u, v, i, l, r;
};

vector<qs> queries;
vector<qs> st[SZ];
ll dist[SZ];
vector<pair<ll, ll>> srt;

void djikstra() {
    set<pair<ll, ll>> st;
    for (int i = 0; i < n; i++) dist[i] = INF;
    for (auto c : bad) dist[c] = 0;

    for (int i = 0; i < n; i++) st.insert({ dist[i], i });

    while (!st.empty()) {
        pair<ll, ll> v = (*st.begin());
        st.erase(st.begin());

        for (auto to : gr[v.second]) {
            if (dist[to.first] > v.first + to.second) {
                st.erase({ dist[to.first], to.first });
                dist[to.first] = v.first + to.second;
                st.insert({ dist[to.first], to.first });
            }
        }
    }

    for (int i = 0; i < n; i++) srt.push_back({ dist[i], i });
    sort(srt.rbegin(), srt.rend());
}

ll par(int v) {
    if (dsu[v] == v) return v;
    else return dsu[v] = par(dsu[v]);
}

void uni(int v, int u) {
    v = par(v);
    u = par(u);
    if (v != u) {
        dsu[v] = u;
    }
}
void add(int v) {
    for (auto to : gr[v]) {
        if (dist[to.first] >= dist[v]) uni(to.first, v);
    }
}
signed main() {
    fastInp;

    cin >> n >> m;
    gr.resize(n);

    for (int i = 0; i < m; i++) {
        ll u, v, c;
        cin >> u >> v >> c;
        u--; v--;
        gr[u].push_back({ v, c });
        gr[v].push_back({ u, c });
    }

    cin >> k;
    bad.resize(k);
    for (auto& c : bad) cin >> c;

    djikstra();
    ll q;
    cin >> q;

    int md = (n - 1) / 2;

    for (int i = 0; i < q; i++) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        queries.push_back({ u, v, i, -1, n });
        st[md].push_back({ u, v, i, -1, n });
    }

    vector<ll> ans(q);
    for (int j = 0; j < LG; j++) {
        for (int i = 0; i < n; i++) dsu[i] = i;
        for (int i = 0; i <= n; i++) {
            if (i >= 1) {
                add(i - 1);
            }

            while (!st[i].empty()) {
                qs cur = st[i].back();
                st[i].pop_back();

                if (par(cur.u) == par(cur.v)) {
                    cur.r = i;
                } else {
                    cur.l = i;
                }

                if (cur.l == cur.r - 1) {
                    ans[cur.i] = dist[cur.l];
                    continue;
                }
                int md2 = (cur.r + cur.l) / 2;
                st[md2].push_back(cur);
            }
        }
    }

    for (auto c : ans) cout << c << "\n";

    return 0;
}

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