oj.uz

Submission #769944

# Submission time Handle Problem Language Result Execution time Memory
769944 2023-06-30T14:29:30 Z adrilen Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 890 ms 123572 KB 
#include "crocodile.h"
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<ll, 2>;
using arrr = array<ll, 3>;

constexpr int maxn = 2e5;

basic_string <arr> adj[maxn];

int visited[maxn] = { 0 };

ll val[maxn] = { 0 };
 


int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
    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]});
    }  

    priority_queue<arr, vector<arr>, greater<arr>> pq;

    for (int i = 0; i < k; i++) 
    {
        visited[P[i]] = 1;
        pq.emplace(arr{0, P[i]});
    }

    arr p;
    ll pos, value;
    while (!pq.empty())
    {
        p = pq.top();
        pq.pop();
        pos = p[1], value = p[0];

        visited[pos]++;
        // cout << value << " " << pos <<" " << visited[pos]<< "\n";

        if (visited[pos] != 2) continue;

        val[pos] = value;

        for (auto i : adj[pos])
        {
            pq.emplace(arr{value + i[1], i[0]});
        }
    }

    return val[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 4 ms 6612 KB Output is correct
6 Correct 3 ms 6592 KB Output is correct
7 Correct 4 ms 6612 KB Output is correct
8 Correct 4 ms 6724 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 4 ms 6612 KB Output is correct
6 Correct 3 ms 6592 KB Output is correct
7 Correct 4 ms 6612 KB Output is correct
8 Correct 4 ms 6724 KB Output is correct
9 Correct 6 ms 7252 KB Output is correct
10 Correct 3 ms 6612 KB Output is correct
11 Correct 4 ms 6736 KB Output is correct
12 Correct 8 ms 7764 KB Output is correct
13 Correct 8 ms 7896 KB Output is correct
14 Correct 3 ms 6612 KB Output is correct
15 Correct 4 ms 6740 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 4 ms 6612 KB Output is correct
6 Correct 3 ms 6592 KB Output is correct
7 Correct 4 ms 6612 KB Output is correct
8 Correct 4 ms 6724 KB Output is correct
9 Correct 6 ms 7252 KB Output is correct
10 Correct 3 ms 6612 KB Output is correct
11 Correct 4 ms 6736 KB Output is correct
12 Correct 8 ms 7764 KB Output is correct
13 Correct 8 ms 7896 KB Output is correct
14 Correct 3 ms 6612 KB Output is correct
15 Correct 4 ms 6740 KB Output is correct
16 Correct 827 ms 101984 KB Output is correct
17 Correct 76 ms 22744 KB Output is correct
18 Correct 122 ms 25564 KB Output is correct
19 Correct 890 ms 123572 KB Output is correct
20 Correct 550 ms 104804 KB Output is correct
21 Correct 38 ms 13940 KB Output is correct
22 Correct 462 ms 69284 KB Output is correct