oj.uz

Submission #1072110

# Submission time Handle Problem Language Result Execution time Memory
1072110 2024-08-23T14:25:03 Z Icelast Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 503 ms 97028 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
vector<pair<ll, ll>> dijkstra(vector<int> s, vector<vector<pair<ll, ll>>> &adj){
    int n = adj.size();
    vector<pair<ll, ll>> dist(n+1, {INF, INF});
    vector<bool> vis(n+1, false);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    for(int i : s){
        dist[i] = {0, 0};
        pq.push({0, i});
    }
    while(!pq.empty()){
        ll d_u = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if(vis[u]){
            continue;
        }
        vis[u] = true;
        for(auto it : adj[u]){
            int v = it.first;
            ll w = it.second;
            if(vis[v]) continue;
            ll fetch = d_u+w;
            if(dist[v].first > fetch){
                swap(dist[v].first, fetch);
            }
            if(dist[v].second > fetch){
                swap(dist[v].second, fetch);
            }
            if(dist[v].second < 1e18){
                pq.push({dist[v].second, v});
            }
        }
    }
    return dist;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    int n = N, m = M;
    vector<vector<pair<ll, ll>>> adj(n+1);
    for(int i = 1; i <= m; i++){
        int u = R[i-1][0], v = R[i-1][1], w = L[i-1];
        u++; v++;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    vector<int> s;
    for(int i = 1; i <= K; i++){
        s.push_back(P[i-1]+1);
    }
    vector<pair<ll, ll>> dist = dijkstra(s, adj);
    return dist[1].second;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 7 ms 5212 KB Output is correct
13 Correct 4 ms 5212 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4556 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 7 ms 5212 KB Output is correct
13 Correct 4 ms 5212 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4556 KB Output is correct
16 Correct 503 ms 97028 KB Output is correct
17 Correct 51 ms 19544 KB Output is correct
18 Correct 87 ms 21844 KB Output is correct
19 Correct 453 ms 95280 KB Output is correct
20 Correct 314 ms 75456 KB Output is correct
21 Correct 24 ms 11240 KB Output is correct
22 Correct 311 ms 64340 KB Output is correct