oj.uz

Submission #574201

# Submission time Handle Problem Language Result Execution time Memory
574201 2022-06-08T07:27:40 Z keta_tsimakuridze Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 454 ms 63412 KB 
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
const int maxn = 2e5 + 5, inf = 2e9 + 5;
vector<pii> V[maxn];
int d[maxn][2];
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];
        V[u].push_back({v, L[i]});
        V[v].push_back({u, L[i]});
    }
    for(int i = 0; i < N; i++) {
        d[i][0] = d[i][1] = inf;
    }
    priority_queue<pii, vector<pii>, greater<pii> > q;
    for(int i = 0; i < K; i++) d[P[i]][0] = d[P[i]][1] = 0, q.push({0, P[i]});

    while(q.size()) {
        int di = q.top().f, u = q.top().s;
        q.pop();
        if(di > d[u][1]) continue;
        for(int i = 0; i < V[u].size(); ++i) {
            int v = V[u][i].f;
            if(d[v][0] > di + V[u][i].s) {
                if(d[v][1] > d[v][0]) d[v][1] = d[v][0], q.push({d[v][1], v});
                d[v][0] = di + V[u][i].s;
            }
            else if(d[v][1]  > di + V[u][i].s) {
                d[v][1] = di + V[u][i].s;
                 q.push({d[v][1], v});
            }
        }
    } 
    return d[0][1];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int i = 0; i < V[u].size(); ++i) {
      |                        ~~^~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 4 ms 5276 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 6 ms 5460 KB Output is correct
13 Correct 5 ms 5460 KB Output is correct
14 Correct 3 ms 5012 KB Output is correct
15 Correct 4 ms 5076 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 4 ms 5276 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 6 ms 5460 KB Output is correct
13 Correct 5 ms 5460 KB Output is correct
14 Correct 3 ms 5012 KB Output is correct
15 Correct 4 ms 5076 KB Output is correct
16 Correct 368 ms 59580 KB Output is correct
17 Correct 75 ms 16088 KB Output is correct
18 Correct 82 ms 17480 KB Output is correct
19 Correct 454 ms 63412 KB Output is correct
20 Correct 279 ms 51964 KB Output is correct
21 Correct 39 ms 9992 KB Output is correct
22 Correct 270 ms 48300 KB Output is correct