oj.uz

Submission #713447

# Submission time Handle Problem Language Result Execution time Memory
713447 2023-03-22T03:33:23 Z That_Salamander Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 725 ms 101536 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,up) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)
#define int long long

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

vector<vector<pii>> conn;
vi a, b;
vector<bool> v;

signed travel_plan(signed n, signed m, signed R[][2], signed L[], signed k, signed P[]) {
    conn.resize(n);
    a.resize(n, 1000000000000ll);
    b.resize(n, 1000000000000ll);
    v.resize(n);

    for (int i = 0; i < m; i++) {
        int t, f, w;
        t = R[i][0];
        f = R[i][1];
        w = L[i];
        conn[t].push_back({f, w});
        conn[f].push_back({t, w});
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

    for (int i = 0; i < k; i++) {
        int x;
        x = P[i];

        q.push({0, x});
    }

    while (!q.empty()) {
        auto p = q.top(); q.pop();
        int cost = p.first;
        int room = p.second;

        if (room == 0) {
            return cost;
        }

        if (v[room]) continue;
        v[room] = true;

        for (auto c: conn[room]) {
            int to = c.first;
            int time = cost + c.second;

            if (a[to] > time) {
                b[to] = a[to];
                a[to] = time;
            } else if (b[to] > time) {
                b[to] = time;
            }

            q.push({b[to], to});
        }
    }
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:41:85: warning: control reaches end of non-void function [-Wreturn-type]
   41 |     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
      |                                                                                     ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 3 ms 820 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 6 ms 1184 KB Output is correct
13 Correct 3 ms 1084 KB Output is correct
14 Correct 1 ms 356 KB Output is correct
15 Correct 2 ms 468 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 3 ms 820 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 6 ms 1184 KB Output is correct
13 Correct 3 ms 1084 KB Output is correct
14 Correct 1 ms 356 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 725 ms 95944 KB Output is correct
17 Correct 105 ms 19832 KB Output is correct
18 Correct 98 ms 21248 KB Output is correct
19 Correct 572 ms 101536 KB Output is correct
20 Correct 266 ms 65452 KB Output is correct
21 Correct 56 ms 8768 KB Output is correct
22 Correct 501 ms 63460 KB Output is correct