Submission #1139049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139049		anmattroi	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	549 ms	55208 KiB

crocodile

#include "crocodile.h"
#define fi first
#define se second
#define maxn 100005
#define maxm 1000005
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;

struct edge {
    int u, v, l;
    edge() {}
    edge(int _u, int _v, int _l) : u(_u), v(_v), l(_l) {}
} edges[maxm];

int n, m, k;
int p[maxn];
vector<ii> adj[maxn];
ii kc[maxn];

ii f(ii x, int y) {
    ii cr = x;
    if (cr.fi >= y) {
        cr.se = cr.fi;
        cr.fi = y;
    } else if (cr.se >= y) cr.se = y;
    return cr;
}

void modified_dijkstra() {
    set<pair<int, int> > q;

    for (int i = 0; i < k; i++) {
        int u = p[i];
        kc[u] = {0, 0};
        q.insert({0, u});
    }

    while (!q.empty()) {
        int u = q.begin()->se; q.erase(q.begin());
        for (auto [v, l] : adj[u]) {
            ii fg = f(kc[v], kc[u].se+l);
            if (kc[v].se > fg.se) {
                q.erase({kc[v].se, v});
                q.insert({fg.se, v});
            }
            kc[v] = fg;
        }
    }
}

int solve() {
    for (int i = 0; i < n; i++) kc[i] = {INT_MAX, INT_MAX};
    for (int i = 0; i < m; i++) {
        auto [u, v, l] = edges[i];
        adj[u].emplace_back(v, l);
        adj[v].emplace_back(u, l);
    }
    modified_dijkstra();
    return kc[0].se;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n = N; m = M; k = K;
    for (int i = 0; i < k; i++) p[i] = P[i];
    for (int i = 0; i < m; i++) edges[i] = edge(R[i][0], R[i][1], L[i]);
    return solve();
}
/*
5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14
*/

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