oj.uz

Submission #743940

# Submission time Handle Problem Language Result Execution time Memory
743940 2023-05-18T06:24:36 Z josanneo22 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 480 ms 52672 KB 
#include <bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second  

const int mxn = 1e5;
const int inf = 1e9 + 3;
vector<pii>adj[mxn + 1];
pii d[mxn + 1]; // best and second best
struct ch {
    int u, d;
};
struct cmp {
    bool operator()(ch a, ch b) {
        return(a.d > b.d);
    }
};

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
    for (int i = 0; i < n; i++) {
        d[i].fi = d[i].se = inf;
    }
    for (int i = 0; i < m; i++) {
        int u = r[i][0], v = r[i][1], w = l[i];
        adj[u].pb({ v, w }); adj[v].pb({ u, w });
    }
    priority_queue<ch, vector<ch>, cmp>pq;
    for (int i = 0; i < k; i++) {
        d[p[i]].fi = d[p[i]].se = 0;
        pq.push({ p[i], 0 });
    }
    while (!pq.empty()) {
        ch nw = pq.top(); pq.pop();
        int u = nw.u, dd = nw.d;
        if (u == 0) {
            return (dd);
        }
        if (d[u].se < dd)continue;
        for (auto i : adj[u]) {
            int v = i.fi, w = i.se;
            if (dd + w < d[v].se) {
                int cr = d[v].se;
                d[v].se = dd + w;
                if (d[v].fi > d[v].se) swap(d[v].fi, d[v].se);
                if (d[v].se < cr) {
                    pq.push({ v, d[v].se });
                }
            }
        }
    }
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:34:40: warning: control reaches end of non-void function [-Wreturn-type]
   34 |     priority_queue<ch, vector<ch>, cmp>pq;
      |                                        ^~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2600 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 4 ms 2900 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2676 KB Output is correct
12 Correct 5 ms 3156 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2676 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2600 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 4 ms 2900 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2676 KB Output is correct
12 Correct 5 ms 3156 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2676 KB Output is correct
16 Correct 426 ms 48812 KB Output is correct
17 Correct 73 ms 13676 KB Output is correct
18 Correct 81 ms 15164 KB Output is correct
19 Correct 480 ms 52672 KB Output is correct
20 Correct 288 ms 43684 KB Output is correct
21 Correct 45 ms 7668 KB Output is correct
22 Correct 297 ms 38892 KB Output is correct