oj.uz

Submission #426166

# Submission time Handle Problem Language Result Execution time Memory
426166 2021-06-13T14:49:18 Z JeanBombeur Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 940 ms 86604 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({- DistMin[dest.first].second, 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 (int)DistMin[0].second;
}

Subtask #1
46.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 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct

Subtask #2
43.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 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 6 ms 3148 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2828 KB Output is correct
12 Correct 7 ms 3568 KB Output is correct
13 Correct 7 ms 3660 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct

Subtask #3
11.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 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 6 ms 3148 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2828 KB Output is correct
12 Correct 7 ms 3568 KB Output is correct
13 Correct 7 ms 3660 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct
16 Correct 790 ms 86604 KB Output is correct
17 Correct 87 ms 17616 KB Output is correct
18 Correct 134 ms 20208 KB Output is correct
19 Correct 940 ms 82732 KB Output is correct
20 Correct 545 ms 69176 KB Output is correct
21 Correct 49 ms 9724 KB Output is correct
22 Correct 461 ms 55648 KB Output is correct