oj.uz

Submission #51110

# Submission time Handle Problem Language Result Execution time Memory
51110 2018-06-16T04:53:03 Z 강태규(#1289, imeimi2000) Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 769 ms 45100 KB 
#include "crocodile.h"
#include <vector>
#include <queue>

using namespace std;
typedef long long llong;

struct _edge {
    int x, c;
    _edge(int x, int c) : x(x), c(c) {}
    bool operator<(const _edge &p) const {
        return c > p.c;
    }
};

const int MAXN = 1e5 + 1;
const int inf = 1e9 + 7;
vector<_edge> edge[MAXN];
int dist1[MAXN];
int dist2[MAXN];
priority_queue<_edge> pq;

int pushDist(int x, int d) {
    if (d < dist1[x]) {
        dist2[x] = dist1[x];
        dist1[x] = d;
        pq.emplace(x, d);
    }
    else if (d < dist2[x]) {
        dist2[x] = d;
        if (dist1[x] < d) pq.emplace(x, d);
    }
}

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) {
    for (int i = 0; i < n; ++i) {
        dist1[i] = dist2[i] = inf;
    }
    for (int i = 0; i < m; ++i) {
        edge[R[i][0]].emplace_back(R[i][1], L[i]);
        edge[R[i][1]].emplace_back(R[i][0], L[i]);
    }
    for (int i = 0; i < k; ++i) {
        dist1[P[i]] = dist2[P[i]] = 0;
        pq.emplace(P[i], 0);
    }
    
    while (!pq.empty()) {
        _edge t = pq.top();
        pq.pop();
        if (t.c != dist2[t.x]) continue;
        if (t.x == 0) {
            return t.c;
        }
        for (_edge i : edge[t.x]) pushDist(i.x, t.c + i.c);
    }
    
    return -1;
}

Compilation message

crocodile.cpp: In function 'int pushDist(int, int)':
crocodile.cpp:33:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2792 KB Output is correct
3 Correct 4 ms 2976 KB Output is correct
4 Correct 5 ms 2976 KB Output is correct
5 Correct 5 ms 2976 KB Output is correct
6 Correct 4 ms 2976 KB Output is correct
7 Correct 5 ms 2976 KB Output is correct
8 Correct 4 ms 2980 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2792 KB Output is correct
3 Correct 4 ms 2976 KB Output is correct
4 Correct 5 ms 2976 KB Output is correct
5 Correct 5 ms 2976 KB Output is correct
6 Correct 4 ms 2976 KB Output is correct
7 Correct 5 ms 2976 KB Output is correct
8 Correct 4 ms 2980 KB Output is correct
9 Correct 8 ms 3216 KB Output is correct
10 Correct 4 ms 3216 KB Output is correct
11 Correct 5 ms 3216 KB Output is correct
12 Correct 8 ms 3284 KB Output is correct
13 Correct 8 ms 3412 KB Output is correct
14 Correct 4 ms 3412 KB Output is correct
15 Correct 6 ms 3412 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2792 KB Output is correct
3 Correct 4 ms 2976 KB Output is correct
4 Correct 5 ms 2976 KB Output is correct
5 Correct 5 ms 2976 KB Output is correct
6 Correct 4 ms 2976 KB Output is correct
7 Correct 5 ms 2976 KB Output is correct
8 Correct 4 ms 2980 KB Output is correct
9 Correct 8 ms 3216 KB Output is correct
10 Correct 4 ms 3216 KB Output is correct
11 Correct 5 ms 3216 KB Output is correct
12 Correct 8 ms 3284 KB Output is correct
13 Correct 8 ms 3412 KB Output is correct
14 Correct 4 ms 3412 KB Output is correct
15 Correct 6 ms 3412 KB Output is correct
16 Correct 672 ms 42284 KB Output is correct
17 Correct 113 ms 42284 KB Output is correct
18 Correct 136 ms 42284 KB Output is correct
19 Correct 769 ms 45100 KB Output is correct
20 Correct 344 ms 45100 KB Output is correct
21 Correct 58 ms 45100 KB Output is correct
22 Correct 431 ms 45100 KB Output is correct