oj.uz

Submission #679335

# Submission time Handle Problem Language Result Execution time Memory
679335 2023-01-08T04:50:31 Z Cross_Ratio Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 496 ms 75028 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
int N, M, K;
vector<vector<array<int, 2>>> adj;
int E[1000005][3];
bool on[100005];
int dis[100005][2];
typedef pair<int,int> P;
bool vis[100005];
int travel_plan(int _N, int _M, int _R[][2], int _L[], int _K, int _P[]) {
    N = _N, M = _M, K = _K;
    adj.resize(N);
    int i, j;
    for(i=0;i<M;i++) {
        E[i][0] = _R[i][0], E[i][1] = _R[i][1];
        E[i][2] = _L[i];
    }
    for(i=0;i<M;i++) {
        adj[E[i][0]].push_back({E[i][1], E[i][2]});
        adj[E[i][1]].push_back({E[i][0], E[i][2]});
    }
    for(i=0;i<K;i++) {
        on[_P[i]] = true;
    }
    for(i=0;i<N;i++) dis[i][0] = dis[i][1] = INF;
    priority_queue<P, vector<P>, greater<P>> PQ;
    for(i=0;i<N;i++) {
        if(on[i]) {
            dis[i][0] = dis[i][1] = 0;
            PQ.push(P(dis[i][1], i));
        }
    }
    while(!PQ.empty()) {
        P k = PQ.top();
        PQ.pop();
        int id = k.second;
        if(vis[id]) continue;
        vis[id] = true;
        for(auto it : adj[id]) {
            int d = dis[id][1] + it[1];
            int n = it[0];
            if(dis[n][0] >= d) {
                dis[n][1] = dis[n][0];
                dis[n][0] = d;
                PQ.push(P(dis[n][1], n));
            }
            else if(dis[n][1] > d) {
                dis[n][1] = d;
                PQ.push(P(dis[n][1], n));
            }
        }
    }
    return dis[0][1];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:15:12: warning: unused variable 'j' [-Wunused-variable]
   15 |     int i, j;
      |            ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 468 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 3 ms 980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 460 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 3 ms 980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 379 ms 68780 KB Output is correct
17 Correct 83 ms 17236 KB Output is correct
18 Correct 101 ms 18972 KB Output is correct
19 Correct 496 ms 75028 KB Output is correct
20 Correct 253 ms 59056 KB Output is correct
21 Correct 38 ms 7424 KB Output is correct
22 Correct 273 ms 55256 KB Output is correct