oj.uz

Submission #384947

# Submission time Handle Problem Language Result Execution time Memory
384947 2021-04-02T18:03:16 Z izhang05 Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 5 ms 1132 KB 
#include "crocodile.h"
#ifdef LOCAL
#include "crocodile_grader.cpp"
#endif

#include <bits/stdc++.h>

using namespace std;
#define int long long
//#define DEBUG
const int maxn = 1e3 + 5, inf = 1e18;
int sol[maxn];
vector<pair<int, int>> adj[maxn];
pair<int, int> c[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});
    }
}

signed travel_plan(signed n, signed m, signed r[][2], signed l[], signed k, signed 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;
        for (auto j : adj[p[i]]) {
            comb(j.first, j.second);
        }
    }
    while (sol[0] == inf) {
        pair<int, int> cur = *q.begin();
        int node = cur.second, cost = cur.first;
        sol[node] = cur.first;
        q.erase(q.begin());
        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 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 5 ms 1132 KB Output is correct
13 Correct 4 ms 1132 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Incorrect 2 ms 492 KB Output isn't correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 5 ms 1132 KB Output is correct
13 Correct 4 ms 1132 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Incorrect 2 ms 492 KB Output isn't correct