oj.uz

Submission #1013436

# Submission time Handle Problem Language Result Execution time Memory
1013436 2024-07-03T14:32:37 Z Error404 Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 2000 ms 6492 KB 
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define f first
#define s second
#define pi pair<ll,ll>
#define vi vector<ll>
#define vpi vector<pi>
#define pb push_back
#define INF 1000000000000
#define endl '\n'
//#define int ll
#define pii pair<pi,ll>

const int MAX = 1e5+1;

vpi g[MAX];
ll dis[MAX][2];



ll travel_plan(int n,int m, int R[][2], int L[],int k, int P[]){
    ll a,b,c,from;
    for(int i = 0; i < m; i++){
       a = R[i][0];
       b = R[i][1];
       c = L[i];
       g[a].pb({b,c});
       g[b].pb({a,c});
    }

    priority_queue<pii, vector<pii>, greater<pii>>pq;
     for(int i = 0; i < n; i++){
        dis[i][0]=INF;
        dis[i][1]=INF;
    }

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

   

    while(!pq.empty()){
        a = pq.top().f.f;
        b = pq.top().f.s;
        from = pq.top().s;
        for(pi i : g[from]){
            int to = i.f;
            int w= i.s;
      
            if(dis[to][0]>= b+w){
                dis[to][1] = dis[to][0];
                dis[to][0] = b+w;
                pq.push({{dis[to][0],dis[to][1]}, to});
            }
            else if(dis[to][1]>=b+w){
                dis[to][1] = b+w;  
                pq.push({{dis[to][0],dis[to][1]}, to});
            }
        }
        pq.pop();
    }

    if(dis[0][1]==INF) return -1;
    else return dis[0][1]; 

}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Execution timed out 2091 ms 6492 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Execution timed out 2091 ms 6492 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Execution timed out 2091 ms 6492 KB Time limit exceeded
3 Halted 0 ms 0 KB -