oj.uz

Submission #477541

# Submission time Handle Problem Language Result Execution time Memory
477541 2021-10-02T13:48:59 Z RambaXGorilla Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 655 ms 72796 KB 
#include<cstdio>
#include<climits>
#include<algorithm>
#include<functional>
#include<utility>
#include<vector>
#include<queue>
using namespace std;
typedef pair <int,int> ii;
#define pq priority_queue
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    vector <ii> adj[100010];
    int dists[100010];
    pq <ii, vector <ii>, greater <ii>> least;
    bool once[100010] = {};
    for(int i = 0;i < M;i++){
        adj[R[i][0]].push_back(ii(L[i], R[i][1]));
        adj[R[i][1]].push_back(ii(L[i], R[i][0]));
    }
    fill(dists, dists + 100010, INT_MAX);
    for(int i = 0;i < K;i++){
        least.push(ii(0, P[i]));
        once[P[i]] = true;
    }
    while(!least.empty()){
        int d = least.top().first;
        int u = least.top().second;
        least.pop();
        if(dists[u] != INT_MAX){
            continue;
        }
        if(!once[u]){
            once[u] = true;
            continue;
        }
        if(!u){
            return d;
        }
        dists[u] = d;
        for(int i = 0;i < adj[u].size();i++){
            int e = adj[u][i].first;
            int v = adj[u][i].second;
            least.push(ii(d + e, v));
        }
    }
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:40:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int i = 0;i < adj[u].size();i++){
      |                       ~~^~~~~~~~~~~~~~~
crocodile.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
   46 | }
      | ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3152 KB Output is correct
2 Correct 2 ms 3112 KB Output is correct
3 Correct 2 ms 3116 KB Output is correct
4 Correct 3 ms 3152 KB Output is correct
5 Correct 3 ms 3120 KB Output is correct
6 Correct 3 ms 3152 KB Output is correct
7 Correct 3 ms 3152 KB Output is correct
8 Correct 3 ms 3152 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3152 KB Output is correct
2 Correct 2 ms 3112 KB Output is correct
3 Correct 2 ms 3116 KB Output is correct
4 Correct 3 ms 3152 KB Output is correct
5 Correct 3 ms 3120 KB Output is correct
6 Correct 3 ms 3152 KB Output is correct
7 Correct 3 ms 3152 KB Output is correct
8 Correct 3 ms 3152 KB Output is correct
9 Correct 5 ms 3408 KB Output is correct
10 Correct 2 ms 3152 KB Output is correct
11 Correct 3 ms 3280 KB Output is correct
12 Correct 7 ms 3920 KB Output is correct
13 Correct 6 ms 3644 KB Output is correct
14 Correct 2 ms 3152 KB Output is correct
15 Correct 3 ms 3152 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3152 KB Output is correct
2 Correct 2 ms 3112 KB Output is correct
3 Correct 2 ms 3116 KB Output is correct
4 Correct 3 ms 3152 KB Output is correct
5 Correct 3 ms 3120 KB Output is correct
6 Correct 3 ms 3152 KB Output is correct
7 Correct 3 ms 3152 KB Output is correct
8 Correct 3 ms 3152 KB Output is correct
9 Correct 5 ms 3408 KB Output is correct
10 Correct 2 ms 3152 KB Output is correct
11 Correct 3 ms 3280 KB Output is correct
12 Correct 7 ms 3920 KB Output is correct
13 Correct 6 ms 3644 KB Output is correct
14 Correct 2 ms 3152 KB Output is correct
15 Correct 3 ms 3152 KB Output is correct
16 Correct 554 ms 72796 KB Output is correct
17 Correct 95 ms 13508 KB Output is correct
18 Correct 112 ms 15044 KB Output is correct
19 Correct 655 ms 67012 KB Output is correct
20 Correct 308 ms 49956 KB Output is correct
21 Correct 67 ms 7908 KB Output is correct
22 Correct 643 ms 46784 KB Output is correct