oj.uz

Submission #384957

# Submission time Handle Problem Language Result Execution time Memory
384957 2021-04-02T18:12:44 Z izhang05 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 873 ms 60140 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[]) {
    q.erase({-5, -5});
    q.erase({-5, -5});
    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 2 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 4 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 4 ms 2796 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 4 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 4 ms 2796 KB Output is correct
9 Correct 4 ms 2924 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 6 ms 3052 KB Output is correct
13 Correct 6 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 2 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 4 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 4 ms 2796 KB Output is correct
9 Correct 4 ms 2924 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 6 ms 3052 KB Output is correct
13 Correct 6 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 627 ms 40520 KB Output is correct
17 Correct 85 ms 14220 KB Output is correct
18 Correct 95 ms 15724 KB Output is correct
19 Correct 873 ms 60140 KB Output is correct
20 Correct 313 ms 49620 KB Output is correct
21 Correct 45 ms 7916 KB Output is correct
22 Correct 350 ms 46188 KB Output is correct