Submission #41838

#	Time	Username	Problem	Language	Result	Execution time	Memory
41838		nickyrio	Evacuation plan (IZhO18_plan)	C++14	0 / 100	2143 ms	58100 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;
long long d[N];
int fUnion[N], p[N];
vector<int> Query[N];
int l[N], r[N], s[N], t[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() {
    scanf("%d %d", &n, &m);
    REP(i, m) {
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
        e[u].push_back(pp(v, c));
        e[v].push_back(pp(u, c));
    }
    int k;
    scanf("%d", &k);
    FOR(i, 1, n) d[i] = 1e18;
    REP(i, k) {
        int x;
        cin >> x;
        heap.push(pp(d[x] = 0, x));
    }
    while (!heap.empty()) {
        int u = heap.top().second;
        long long dis = -heap.top().first;
        heap.pop();
        if (dis != d[u]) continue;
        for (pp t : e[u]) {
            long long 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;
    Arr(p, 1, n);
    Arr(d, 1, n);
    sort(p + 1, p + n + 1, [] (const int &a, const int &b) {
        return d[a] > d[b];
    });
    Arr(p, 1, n);
    //Read query
    int q;
    scanf("%d", &q);
    FOR(i, 1, q) scanf("%d %d", &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] + 1 < 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])) r[x] = i;
                else l[x] = i;
            }
        }
    }
    FOR(i, 1, q) printf("%lld\n", d[p[r[i]]]);
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &u, &v, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
plan.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
plan.cpp:72:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, q) scanf("%d %d", &s[i], &t[i]);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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