oj.uz

Submission #769942

# Submission time Handle Problem Language Result Execution time Memory
769942 2023-06-30T14:28:50 Z adrilen Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 218 ms 40516 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 = 1e3;

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 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 468 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 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 5 ms 1620 KB Output is correct
13 Correct 5 ms 1756 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 492 KB Output is correct

Subtask #3
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 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 5 ms 1620 KB Output is correct
13 Correct 5 ms 1756 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Runtime error 218 ms 40516 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -