Submission #41841

#	Time	Username	Problem	Language	Result	Execution time	Memory
41841		nickyrio	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1267 ms	76076 KiB

plan

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 1001000
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define all(s) s.begin(), s.end()

using namespace std;

int n, m;
vector<pp> e[N];
priority_queue<pp> heap;
int d[N];
int fUnion[N], p[N];
vector<int> Query[N];
int l[N], r[N], s[N], t[N], cur[N];
bool mark[N];
void Union(int a, int b) {
    int t = fUnion[a] + fUnion[b];
    if (fUnion[a] > fUnion[b]) swap(a, b);
    fUnion[a] = t;
    fUnion[b] = a;
}

int root(int u) { return fUnion[u] < 0 ? u : (fUnion[u] = root(fUnion[u])); }

int main() {
    IO;
    cin >> n >> m;
    REP(i, m) {
        int u, v, c;
        cin >> u >> v >> c;
        e[u].push_back(pp(v, c));
        e[v].push_back(pp(u, c));
    }
    int k;
    cin >> k;
    FOR(i, 1, n) d[i] = 1e9;
    REP(i, k) {
        int x;
        cin >> x;
        heap.push(pp(d[x] = 0, x));
    }
    while (!heap.empty()) {
        int u = heap.top().second;
        int dis = -heap.top().first;
        heap.pop();
        if (dis != d[u]) continue;
        for (pp t : e[u]) {
            int newD = d[u] + t.second;
            int v = t.first;
            if (d[v] > newD) heap.push(pp(-(d[v] = newD), v));
        }
    }
    FOR(i, 1, n) p[i] = i;
    sort(p + 1, p + n + 1, [] (const int &a, const int &b) {
        return d[a] > d[b];
    });
    //Read query
    int q;
    cin >> q;
    FOR(i, 1, q) cin >> s[i] >> t[i];
    //Parallel Binary Search
    FOR(i, 1, q) l[i] = 1, r[i] = n;
    bool changed = true;
    while (changed) {
        changed = false;
        FOR(i, 1, n) {
            Query[i].clear();
            fUnion[i] = -1;
            mark[i] = false;
        }
        FOR(i, 1, q) if (l[i] <= r[i]) {
            Query[(l[i] + r[i]) >> 1].push_back(i);
            changed = true;
        }
        FOR(i, 1, n) {
            int u = p[i];
            mark[u] = true;
            for (pp t : e[u]) {
                int v = t.first;
                if (mark[v]) {
                    int a = root(u);
                    int b = root(v);
                    if (a != b) Union(a, b);
                }
            }
            for (int x : Query[i]) {
                if (root(s[x]) == root(t[x])) cur[x] = i, r[x] = i - 1;
                else l[x] = i + 1;
            }
        }
    }
    FOR(i, 1, q) cout << d[p[cur[i]]] << '\n';
}

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