oj.uz

Submission #384950

# Submission time Handle Problem Language Result Execution time Memory
384950 2021-04-02T18:06:22 Z izhang05 Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 345 ms 40556 KB 
#include "crocodile.h"
#ifdef LOCAL
#include "crocodile_grader.cpp"
#endif

#include <bits/stdc++.h>

using namespace std;
//#define DEBUG
const int maxn = 1e3 + 5, inf = 2e9;
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});
    }
}

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;
        for (auto j : adj[p[i]]) {
            comb(j.first, j.second);
        }
    }
    while (sol[0] == inf) {
        while(sol[q.begin()->second]!=inf){
            q.erase(q.begin());
        }
        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 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 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 364 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 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 364 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 620 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 748 KB Output is correct
13 Correct 4 ms 748 KB Output is correct
14 Correct 2 ms 540 KB Output is correct
15 Correct 2 ms 492 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 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 364 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 620 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 748 KB Output is correct
13 Correct 4 ms 748 KB Output is correct
14 Correct 2 ms 540 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Runtime error 345 ms 40556 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -