oj.uz

Submission #1017887

# Submission time Handle Problem Language Result Execution time Memory
1017887 2024-07-09T11:04:56 Z Kodik Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 326 ms 65672 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ss second
#define ff first
typedef long long ll;
// #define int ll
int mod = 1e9+7;

int travel_plan(int N, int M, int R[][2], 
    int L[], int k, int p[]){
    int n = N, m = M;
    vector<vector<pair<int,int>>> adj(n);
    for(int i = 0; i < m; ++i){
        int a = R[i][0],b = R[i][1],c = L[i];
        adj[a].push_back({c,b});
        adj[b].push_back({c,a});
    }
    for(int i = 0; i < n; ++i){
      sort(adj[i].begin(), adj[i].end());
    }
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    vector<vector<ll>> dis(2,vector<ll>(n, 1e18));
    for(int i = 0; i < k; ++i){
        pq.push({0,p[i]});
        dis[0][p[i]] = 0;
        dis[1][p[i]] = 0;
    }
    while(!pq.empty()){
        pair<int,int> a = pq.top(); pq.pop();
        if(dis[1][a.ss]!=a.ff){
            continue;
        }
        for(auto &[w, nxt] : adj[a.ss]){
            if(a.ff+w<dis[0][nxt]){
                if(dis[0][nxt]!=dis[1][nxt]){
                    pq.push({dis[0][nxt], nxt});
                }
                swap(dis[0][nxt], dis[1][nxt]);
                dis[0][nxt] = a.ff+w;
            }else if(a.ff+w<dis[1][nxt]){
                dis[1][nxt] = a.ff+w;
                pq.push({dis[1][nxt], nxt});
            }
        }        
    }
    return dis[1][0];
}

// signed main(){
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     // ifstream cin ("shortcut.in");
//     // ofstream cout ("shortcut.out");
    
//     return 0;   
// }

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 4444 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 4444 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 4444 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 4444 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 4444 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 4444 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 3 ms 4912 KB Output is correct
13 Correct 3 ms 4892 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 1 ms 4444 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 4444 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 4444 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 4444 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 3 ms 4912 KB Output is correct
13 Correct 3 ms 4892 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 299 ms 57708 KB Output is correct
17 Correct 46 ms 16976 KB Output is correct
18 Correct 57 ms 18340 KB Output is correct
19 Correct 326 ms 65672 KB Output is correct
20 Correct 292 ms 47952 KB Output is correct
21 Correct 24 ms 9564 KB Output is correct
22 Correct 239 ms 46440 KB Output is correct