Submission #1109115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109115		nh0902	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	380 ms	96448 KiB

crocodile

#include <bits/stdc++.h>

using namespace std;

const int N = 110000;

long long const inf = 1e16;

vector<pair<int, long long>> g[N];

vector<int> Exit;

int trace1[N], trace2[N];

long long min_dist1[N], min_dist2[N];

bool update(int x, int i, long long d) {
    if (x == trace2[i]) {
        if (min_dist2[i] <= d) {
            return false;
        }
        min_dist2[i] = d;
        if (min_dist1[i] > min_dist2[i]) {
            swap(min_dist1[i], min_dist2[i]);
            swap(trace1[i], trace2[i]);
        }
        return true;
    }

    if (x == trace1[i]) {
        if (min_dist1[i] <= d) {
            return false;
        }
        min_dist1[i] = d;
        return true;
    }

    if (min_dist2[i] <= d) {
        return false;
    }
    min_dist2[i] = d;
    trace2[i] = x;
    if (min_dist1[i] > min_dist2[i]) {
        swap(min_dist1[i], min_dist2[i]);
        swap(trace1[i], trace2[i]);
    }
    return true;
}

int travel_plan(int n, int m, int r[][2], int w[], int k, int e[]) {
    for (int i = 0; i < m; i ++) {
        g[r[i][0]].push_back({r[i][1], w[i]});
        g[r[i][1]].push_back({r[i][0], w[i]});
    }

    for (int i = 0; i < k; i ++) {
        Exit.push_back(e[i]);
    }

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    for (int i = 0; i < n; i ++) {
        min_dist1[i] = min_dist2[i] = inf;
        trace1[i] = n;
        trace2[i] = n;
    }

    for (int a : Exit) {
        min_dist1[a] = min_dist2[a] = 0;
        trace1[a] = a;
        trace2[a] = a;
        pq.push({0, a});
    }

    int x;
    long long d;

    while (!pq.empty()) {
        auto [d, x] = pq.top();
        pq.pop();

        if (d > min_dist2[x]) continue;

        for (pair<int, long long> e : g[x]) {
            if (update(x, e.first, d + e.second)) {
                if (min_dist2[e.first] < inf) {
                    pq.push({min_dist2[e.first], e.first});
                }
            }
        }
    }

    return min_dist2[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |         auto [d, x] = pq.top();
      |              ^
crocodile.cpp:75:9: warning: unused variable 'x' [-Wunused-variable]
   75 |     int x;
      |         ^
crocodile.cpp:76:15: warning: unused variable 'd' [-Wunused-variable]
   76 |     long long d;
      |               ^

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11