oj.uz

Submission #200647

# Submission time Handle Problem Language Result Execution time Memory
200647 2020-02-07T19:19:13 Z DavidDamian Crocodile's Underground City (IOI11_crocodile) C++11
0 / 100
 7 ms 2808 KB 
#include"crocodile.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge
{
    int to;
    int w;
};
vector<edge> adjList[100005];
int first[100005]; //Shortest path to that node from an exit
int second[100005]; //Second shortest path to that node from an exit
struct node
{
    int data;
    int key;
};
bool operator<(const node& a,const node& b)
{
    return a.key<b.key;
}
priority_queue<node> Q;
void relax(int u,int v,int w)
{
    if(second[u]+w<first[v]){
        second[v]=first[v];
        first[v]=second[u]+w;
        node x={v,second[v]};
        Q.push(x);
    }
    else if(second[u]+w<second[v]){
        second[v]=second[u]+w;
        node x={v,second[v]};
        Q.push(x);
    }
}
void dijkstra(int n,int k,int P[])
{
    for(int i=0;i<n;i++){
        first[i]=second[i]=INT_MAX;
    }
    for(int i=0;i<k;i++){
        int u=P[i];
        first[u]=second[u]=0;
        node x={u,0};
        Q.push(x);
    }
    while(Q.size()){
        node u=Q.top();Q.pop();
        if(u.key==INT_MAX) continue;
        for(edge e: adjList[u.data]){
            relax(u.data,e.to,e.w);
        }
    }
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i=0;i<M;i++){
        int u=R[i][0];
        int v=R[i][1];
        edge e={v,L[i]};
        adjList[u].push_back(e);
        e.to=u;
        adjList[v].push_back(e);
    }
    dijkstra(N,K,P);
    int secondBest=second[0];
    return secondBest;
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 7 ms 2808 KB Output is correct
3 Incorrect 6 ms 2680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 7 ms 2808 KB Output is correct
3 Incorrect 6 ms 2680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 7 ms 2808 KB Output is correct
3 Incorrect 6 ms 2680 KB Output isn't correct
4 Halted 0 ms 0 KB -