oj.uz

Submission #254638

# Submission time Handle Problem Language Result Execution time Memory
254638 2020-07-30T11:38:14 Z Sorting Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 639 ms 48388 KB 
//#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

const int k_N = 1e5 + 3;
const int k_Inf = 1e9 + 7;

int n, m, k;
vector<pair<int, int>> adj[k_N];

bool e[k_N];

pair<int, int> d[k_N];

void dijkstra(){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    for(int i = 0; i < n; ++i){
        if(e[i]){
            d[i] = {0, 0};
            pq.push({0, i});
        }
        else d[i] = {k_Inf, k_Inf};
    }

    while(!pq.empty()){
        auto [dist, u] = pq.top();
        pq.pop();

        if(dist != d[u].second) continue;

        for(auto [to, c]: adj[u]){
            int new_d = c + dist;
            if(d[to].second > new_d){
                int pr = d[to].second;
                d[to].second = new_d;
                if(d[to].first > d[to].second)
                    swap(d[to].first, d[to].second);

                if(d[to].second != pr)
                    pq.push({d[to].second, to});
            }
        }
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N;
    m = M;
    k = K;

    for(int i = 0; i < m; ++i){
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }

    for(int i = 0; i < k; ++i)
        e[P[i]] = true;

    dijkstra();

    return d[0].second;
}

/*
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
7
*/

/*
5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14
*/

Compilation message

crocodile.cpp: In function 'void dijkstra()':
crocodile.cpp:28:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [dist, u] = pq.top();
              ^
crocodile.cpp:33:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for(auto [to, c]: adj[u]){
                  ^

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 4 ms 2948 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 6 ms 3116 KB Output is correct
13 Correct 6 ms 3200 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 4 ms 2948 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 6 ms 3116 KB Output is correct
13 Correct 6 ms 3200 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct
16 Correct 520 ms 44532 KB Output is correct
17 Correct 94 ms 13816 KB Output is correct
18 Correct 118 ms 15288 KB Output is correct
19 Correct 639 ms 48388 KB Output is correct
20 Correct 342 ms 40056 KB Output is correct
21 Correct 49 ms 7676 KB Output is correct
22 Correct 371 ms 35316 KB Output is correct