oj.uz

Submission #1003514

# Submission time Handle Problem Language Result Execution time Memory
1003514 2024-06-20T12:12:40 Z rahidilbayramli Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 374 ms 89012 KB 
#include<bits/stdc++.h>
#include"crocodile.h"
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define all(v) v.begin(), v.end()
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int sz = 1e5+5;
vector<pii>g[sz];
int vis[sz], e[sz], k = 0, i;
ll dist[sz], res = 0;
priority_queue<pll>pq;
void dijkstra()
{
    while(!pq.empty())
    {
        ll dist = pq.top().f;
        ll node = pq.top().s;
        pq.pop();
        vis[node]++;
        if(vis[node] == 2){
            if(node == 0)
            {
                res = -dist;
                return;
            }
            for(auto [u, w] : g[node])
                pq.push({dist - w, u});
        }
    }
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    res = 0;
    for(i = 0; i < M; i++)
    {
        g[R[i][0]].pb({R[i][1], L[i]});
        g[R[i][1]].pb({R[i][0], L[i]});
    }
    for(i = 0; i < K; i++)
    {
      	vis[P[i]] = 1;
      	pq.push({0, P[i]});
    }
  	dijkstra();
    return res;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2836 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 2 ms 2920 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2836 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 2 ms 2920 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 2 ms 3144 KB Output is correct
10 Correct 1 ms 2720 KB Output is correct
11 Correct 2 ms 2908 KB Output is correct
12 Correct 5 ms 3804 KB Output is correct
13 Correct 3 ms 3800 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 2 ms 2908 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2836 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 2 ms 2920 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 2 ms 3144 KB Output is correct
10 Correct 1 ms 2720 KB Output is correct
11 Correct 2 ms 2908 KB Output is correct
12 Correct 5 ms 3804 KB Output is correct
13 Correct 3 ms 3800 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 2 ms 2908 KB Output is correct
16 Correct 304 ms 89012 KB Output is correct
17 Correct 51 ms 13500 KB Output is correct
18 Correct 54 ms 14808 KB Output is correct
19 Correct 325 ms 75096 KB Output is correct
20 Correct 243 ms 82580 KB Output is correct
21 Correct 28 ms 7516 KB Output is correct
22 Correct 374 ms 46976 KB Output is correct