oj.uz

Submission #1013463

# Submission time Handle Problem Language Result Execution time Memory
1013463 2024-07-03T14:48:55 Z Error404 Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 2 ms 2908 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<pi, vector<pi>, greater<pi>>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,P[i]});   
    }

   

    while(!pq.empty()){
        b = pq.top().f;
        from = pq.top().s;

        pq.pop();
        if(b!=dis[from][1]) {
            continue;
        }
        for(pi i : g[from]){
            int to = i.f;
            int w= i.s;
      
            if(dis[to][0]>= b+w){
                bool flag = false;
                if(dis[to][0]!=INF) flag = true;
                dis[to][1] = dis[to][0];
                dis[to][0] = b+w;
                if(flag)pq.push({dis[to][1], to});
            }
            else if(dis[to][1]>=b+w){
                dis[to][1]=b+w;
                pq.push({dis[to][1], to});
            }
           
        }
       
    }

    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 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Incorrect 2 ms 2908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Incorrect 2 ms 2908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Incorrect 2 ms 2908 KB Output isn't correct
6 Halted 0 ms 0 KB -