oj.uz

Submission #745586

# Submission time Handle Problem Language Result Execution time Memory
745586 2023-05-20T13:43:32 Z Dan4Life Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 466 ms 63492 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
using pii = pair<int,int>;
const int mxN = (int)1e5+10;
const int INF = (int)1e9;
vector<int> exits;
vector<pii> adj[mxN];
int n, m, dis[mxN], dis2[mxN], vis[mxN];
 
int dijkstra(){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    memset(dis,63,sizeof(dis)); memset(dis2,63,sizeof(dis2));
    for(auto u : exits) dis[u]=dis2[u]=0, pq.push({0,u});
    while(!pq.empty()){
        int s = pq.top().second; pq.pop();
        if(vis[s]) continue; vis[s]=1;
        for(auto [u,w] : adj[s]){
            if(dis[u]>dis2[s]+w)
                dis2[u]=dis[u], dis[u]=dis2[s]+w, pq.push({dis2[u],u});
            else if(dis2[u]>dis2[s]+w)
                dis2[u]=dis2[s]+w, pq.push({dis2[u],u});
        }
    }
    return dis2[0];
}
 
int travel_plan(int N, int M, int R[][2], int L[], int k, int p[])
{
    n = N, m = M;
    for(int i = 0; i < m; i++){
        int a = R[i][0], b = R[i][1], c = L[i];
        adj[a].pb({b,c}), adj[b].pb({a,c});
    }
    for(int i = 0; i < k; i++) exits.pb(p[i]);
    return dijkstra();
}

Compilation message

crocodile.cpp: In function 'int dijkstra()':
crocodile.cpp:19:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   19 |         if(vis[s]) continue; vis[s]=1;
      |         ^~
crocodile.cpp:19:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   19 |         if(vis[s]) continue; vis[s]=1;
      |                              ^~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 3 ms 3440 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 3 ms 3412 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 3 ms 3440 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 3 ms 3412 KB Output is correct
9 Correct 3 ms 3700 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 5 ms 3852 KB Output is correct
13 Correct 5 ms 3924 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 3 ms 3540 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 3 ms 3440 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 3 ms 3412 KB Output is correct
9 Correct 3 ms 3700 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 5 ms 3852 KB Output is correct
13 Correct 5 ms 3924 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 3 ms 3540 KB Output is correct
16 Correct 380 ms 44864 KB Output is correct
17 Correct 83 ms 15080 KB Output is correct
18 Correct 96 ms 16684 KB Output is correct
19 Correct 466 ms 63492 KB Output is correct
20 Correct 251 ms 50316 KB Output is correct
21 Correct 40 ms 8636 KB Output is correct
22 Correct 263 ms 47044 KB Output is correct