Submission #1266467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266467		BlockOG	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	1840 ms	126924 KiB

crocodile

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! it's free on steam

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

map<int, int> adj[100000];
set<int> exits;
int dist[100000];
int dista[100000];
int distb[100000];
int par[100000];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
    fo(i, 0, m) {
        adj[r[i][0]][r[i][1]] = l[i];
        adj[r[i][1]][r[i][0]] = l[i];
    }

    fo(i, 0, n) dist[i] = dista[i] = distb[i] = 1000000001;

    {
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
        fo(i, 0, k) {
            q.push({0, {p[i], -1}});
            q.push({0, {p[i], -1}});
            exits.insert(p[i]);
        }
        while (q.size()) {
            auto [d, e] = q.top();
            auto [i, p] = e;
            q.pop();

            if (d >= distb[i]) continue;
            if (dista[i] == 1000000001) {
                dista[i] = d;
                par[i] = p;
                continue;
            }
            distb[i] = d;

            for (auto [j, l] : adj[i]) {
                if (distb[j] != 1000000001) continue;
                q.push({d + l, {j, i}});
            }
        }

        fo(i, 0, n) cerr << par[i] << ' ';
        fo(i, 0, n) if (par[i] != -1) adj[i].erase(par[i]), adj[par[i]].erase(i);
    }

    {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        q.push({0, 0});
        while (q.size()) {
            auto [d, i] = q.top();
            q.pop();

            if (d >= dist[i]) continue;
            dist[i] = d;

            if (exits.count(i)) return d;

            for (auto [j, l] : adj[i]) {
                if (dist[j] != 1000000001) continue;
                q.push({d + l, j});
            }
        }
    }
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
   87 | }
      | ^

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