oj.uz

Submission #666103

# Submission time Handle Problem Language Result Execution time Memory
666103 2022-11-27T15:36:00 Z chanhchuong123 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 450 ms 61068 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}

const int MAXN = 1e5 + 4;
const int INF = 1e9 + 1;
int n, m, k;
int Exit[MAXN];
bool isExit[MAXN];
vector<pair<int, int>> adj[MAXN];


int d[MAXN][2];

struct node {
    int du, u;
    bool operator< (const node &other) const {
        return du > other.du;
    }
};
priority_queue<node> pq;

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
    for (int i = 0; i < m; i++) {
        int u = r[i][0], v = r[i][1], w = l[i];
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }
    for (int i = 0; i < n; i++) d[i][0] = d[i][1] = INF;
    for (int i = 0; i < k; i++) {
        d[p[i]][0] = 0;
        d[p[i]][1] = 0;
        pq.push({0, p[i]});
    }
    while (pq.size()) {
        int du = pq.top().du;
        int u = pq.top().u;
        pq.pop();
        if (d[u][1] != du) continue;

        for (pair<int, int> x: adj[u]) {
            int v = x.fi, w = x.se;
            if (d[v][0] >= du + w) {
                if (mini(d[v][1], d[v][0]))
                    pq.push({d[v][1], v});
                d[v][0] = du + w;
            } else if (d[v][1] > du + w) {
                d[v][1] = du + w;
                pq.push({d[v][1], v});
            }
        }
    }
    return d[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 3 ms 2872 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 4 ms 3156 KB Output is correct
13 Correct 4 ms 3156 KB Output is correct
14 Correct 2 ms 2672 KB Output is correct
15 Correct 3 ms 2684 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 3 ms 2872 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 4 ms 3156 KB Output is correct
13 Correct 4 ms 3156 KB Output is correct
14 Correct 2 ms 2672 KB Output is correct
15 Correct 3 ms 2684 KB Output is correct
16 Correct 362 ms 57232 KB Output is correct
17 Correct 64 ms 13732 KB Output is correct
18 Correct 77 ms 15184 KB Output is correct
19 Correct 450 ms 61068 KB Output is correct
20 Correct 253 ms 49604 KB Output is correct
21 Correct 34 ms 7628 KB Output is correct
22 Correct 254 ms 45988 KB Output is correct