oj.uz

Submission #426154

# Submission time Handle Problem Language Result Execution time Memory
426154 2021-06-13T14:44:40 Z JeanBombeur Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 2 ms 2636 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include "crocodile.h"
using namespace std;

const long long INFINI = (1000 * 1000 * 1000);
const int MAX_NOEUDS = (100 * 1000);

vector <pair <int, long long>> Voisins[MAX_NOEUDS];

pair <long long, long long> DistMin[MAX_NOEUDS];

bool Vu[MAX_NOEUDS];

priority_queue <pair <long long, int>> Dijkstra;

void Push() {
    int noeud = Dijkstra.top().second;
    long long dist = DistMin[noeud].second;
    Dijkstra.pop();
    if (Vu[noeud])
        return;
    Vu[noeud] = true;
    for (pair <int, long long> dest : Voisins[noeud])
    {
        if (!Vu[dest.first])
        {
            long long nouvDist = dist + dest.second;
            if (nouvDist <= DistMin[dest.first].first)
            {
                DistMin[dest.first].second = DistMin[dest.first].first;
                DistMin[dest.first].first = nouvDist;
            }
            else if (nouvDist < DistMin[dest.first].second)
                DistMin[dest.first].second = nouvDist;
            if (DistMin[dest.first].second < INFINI)
                Dijkstra.push({- nouvDist, dest.first});
        }
    }
    return;
}

int travel_plan(int nbNoeuds, int nbAretes, int Aretes[][2], int Longueur[], int nbSorties, int Sorties[]) {
    
    for (int i = 0; i < nbNoeuds; i ++)
    {
        DistMin[i].first = DistMin[i].second = INFINI;
    }
    
    for (int i = 0; i < nbAretes; i ++)
    {
        Voisins[Aretes[i][0]].push_back({Aretes[i][1], (long long)Longueur[i]});
        Voisins[Aretes[i][1]].push_back({Aretes[i][0], (long long)Longueur[i]});
    }
    
    for (int i = 0; i < nbSorties; i ++)
    {
        DistMin[Sorties[i]].first = DistMin[Sorties[i]].second = 0LL;
        Dijkstra.push({0LL, Sorties[i]});
    }
    
    while (!Dijkstra.empty())
    {
        Push();
    }
    
    return DistMin[0].second;
}

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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