Submission #99227

#	Time	Username	Problem	Language	Result	Execution time	Memory
99227		eriksuenderhauf	Crocodile's Underground City (IOI11_crocodile)	C++11	100 / 100	1126 ms	104668 KiB

crocodile

#pragma GCC optimize("O3")
#include "crocodile.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const ll INF = 1e17 + 7;
const int MAXN = 1e5 + 5;
ll dist[MAXN];
vector<pair<int,ll>> adj[MAXN];
priority_queue<ll> mx[MAXN];
int vis[MAXN][2];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
    for (int i = 0; i < m; i++) {
        int u = r[i][0], v = r[i][1];
        adj[u].pb({v, l[i]});
        adj[v].pb({u, l[i]});
    }
    fill(dist, dist + MAXN, INF);
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    for (int i = 0; i < k; i++)
        pq.push({0, p[i]}), dist[p[i]] = 0, vis[p[i]][0] = 1;
    while (!pq.empty()) {
        pair<ll,int> cur = pq.top(); pq.pop();
        if (!vis[cur.se][0]) {
            vis[cur.se][0] = 1;
            continue;
        }
        if (vis[cur.se][1])
            continue;
        vis[cur.se][1] = 1;
        if (cur.se == 0)
            return cur.fi;
        for (pair<int,ll> nx: adj[cur.se]) {
            if (vis[nx.fi][1])
                continue;
            pq.push({cur.fi + nx.se, nx.fi});
        }
    }
    return -1;
}

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