oj.uz

Submission #384959

# Submission time Handle Problem Language Result Execution time Memory
384959 2021-04-02T18:13:49 Z izhang05 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 786 ms 43884 KB 
#include "crocodile.h"
#ifdef LOCAL
#include "crocodile_grader.cpp"
#endif

#include <bits/stdc++.h>

using namespace std;
//#define DEBUG
const int maxn = 1e5 + 5, inf = 2e9;
int sol[maxn];
vector<pair<int, int>> adj[maxn];
pair<int, int> c[maxn];
bool ex[maxn];
set<pair<int, int>> q;

void comb(int node, int cost) {
    if (cost < c[node].first) {
        if (c[node].second != inf) {
            q.erase({c[node].second, node});
        }
        swap(c[node].first, c[node].second);
        c[node].first = cost;
        if (c[node].second != inf) {
            q.insert({c[node].second, node});
        }

    } else if (cost < c[node].second) {
        if (c[node].second != inf) {
            q.erase({c[node].second, node});
        }
        c[node].second = cost;
        q.insert({c[node].second, node});
    }
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
    for (int i = 0; i < m; ++i) {
        int a = r[i][0], b = r[i][1], cost = l[i];
        adj[a].emplace_back(b, cost);
        adj[b].emplace_back(a, cost);
    }
    for (int i = 0; i < n; ++i) {
        sol[i] = inf;
        c[i] = {inf, inf};
    }
    for (int i = 0; i < k; ++i) {
        sol[p[i]] = 0;
        ex[p[i]] = true;
    }
    for (int i = 0; i < k; ++i) {
        for (auto j : adj[p[i]]) {
            if (!ex[j.first]) {
                comb(j.first, j.second);
            }
        }
    }
    while (sol[0] == inf) {
        pair<int, int> cur = *q.begin();
        q.erase(q.begin());
        int node = cur.second, cost = cur.first;
        sol[node] = cur.first;
        for (auto i : adj[node]) {
            if (sol[i.first] == inf) {
                comb(i.first, cost + i.second);
            }
        }
    }
#ifdef DEBUG
    for (int j = 0; j < n; ++j) {
        cout << sol[j] << "\n";
    }
#endif
    return sol[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 4 ms 2924 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 6 ms 3052 KB Output is correct
13 Correct 5 ms 3180 KB Output is correct
14 Correct 3 ms 2668 KB Output is correct
15 Correct 3 ms 2796 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 4 ms 2924 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 6 ms 3052 KB Output is correct
13 Correct 5 ms 3180 KB Output is correct
14 Correct 3 ms 2668 KB Output is correct
15 Correct 3 ms 2796 KB Output is correct
16 Correct 596 ms 40556 KB Output is correct
17 Correct 81 ms 10860 KB Output is correct
18 Correct 93 ms 12396 KB Output is correct
19 Correct 786 ms 43884 KB Output is correct
20 Correct 301 ms 36588 KB Output is correct
21 Correct 42 ms 6508 KB Output is correct
22 Correct 339 ms 31980 KB Output is correct