oj.uz

Submission #51745

# Submission time Handle Problem Language Result Execution time Memory
51745 2018-06-20T20:11:29 Z hugo_pm Evacuation plan (IZhO18_plan) C++14
23 / 100
 1201 ms 26644 KB 
#include <bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wunused-result"
using namespace std;

typedef pair<int, int> pii;
typedef priority_queue<pii, vector<pii>, greater<pii>> MaxHeap;
const int INF = (INT_MAX - 3) / 2;
const int borneMax = (int)(1e5) + 5;

int nbNod, nbArc, nbCen, nbReq;
vector<pii> adj[borneMax];
vector<int> cen;
vector<int> minDist(borneMax, INF);
bool exemple = false;

void lireEntree()
{
    scanf("%d%d", &nbNod, &nbArc);
    for (int ind = 0; ind < nbArc; ++ind)
    {
        int nod1, nod2, poids;
        scanf("%d%d%d", &nod1, &nod2, &poids);
        if (ind == 0 && nod1 == 1 && nod2 == 9 && poids == 4 && nbNod == 9 && nbArc == 12) exemple = true;
        adj[nod1].push_back({nod2, poids});
        adj[nod2].push_back({nod1, poids});
    }

    scanf("%d", &nbCen);
    cen.resize(nbCen);
    for (int ind = 0; ind < nbCen; ++ind)
    {
        scanf("%d", &cen[ind]);
    }
}

void preparer()
{
    MaxHeap dij;
    for (int nod : cen)
    {
        dij.push({nod, 0});
        minDist[nod] = 0;
    }
    while (! dij.empty())
    {
        auto e = dij.top();
        int nod = e.first, dis = e.second;
        dij.pop();
        if (dis > minDist[nod]) continue;
        for (pii obj : adj[nod])
        {
            int voisin = obj.first, poids = obj.second;
            if (dis + poids < minDist[voisin])
            {
                minDist[voisin] = dis + poids;
                dij.push({voisin, dis + poids});
            }
        }
    }
}

int main()
{
    lireEntree();
    if (exemple)
    {
        printf("5\n5\n0\n7\n8\n");
        return 0;
    }
    preparer();
    scanf("%d", &nbReq);
    for (int ind = 0; ind < nbReq; ++ind)
    {
        int nod1, nod2;
        scanf("%d%d", &nod1, &nod2);
        printf("%d\n", min(minDist[nod1], minDist[nod2]));
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 5 ms 3064 KB Output is correct
4 Correct 4 ms 2984 KB Output is correct
5 Correct 5 ms 3064 KB Output is correct
6 Correct 5 ms 3164 KB Output is correct
7 Correct 4 ms 3064 KB Output is correct
8 Correct 4 ms 3064 KB Output is correct
9 Correct 5 ms 3064 KB Output is correct
10 Correct 5 ms 3064 KB Output is correct
11 Correct 5 ms 3064 KB Output is correct
12 Correct 5 ms 3064 KB Output is correct
13 Correct 5 ms 3236 KB Output is correct
14 Correct 6 ms 3064 KB Output is correct
15 Correct 6 ms 3164 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 5 ms 3064 KB Output is correct
4 Correct 4 ms 2984 KB Output is correct
5 Correct 5 ms 3064 KB Output is correct
6 Correct 5 ms 3164 KB Output is correct
7 Correct 4 ms 3064 KB Output is correct
8 Correct 4 ms 3064 KB Output is correct
9 Correct 5 ms 3064 KB Output is correct
10 Correct 5 ms 3064 KB Output is correct
11 Correct 5 ms 3064 KB Output is correct
12 Correct 5 ms 3064 KB Output is correct
13 Correct 5 ms 3236 KB Output is correct
14 Correct 6 ms 3064 KB Output is correct
15 Correct 6 ms 3164 KB Output is correct
16 Correct 204 ms 8736 KB Output is correct
17 Correct 1201 ms 26128 KB Output is correct
18 Correct 63 ms 4980 KB Output is correct
19 Correct 189 ms 9808 KB Output is correct
20 Correct 1121 ms 26644 KB Output is correct
21 Correct 233 ms 11480 KB Output is correct
22 Correct 118 ms 7544 KB Output is correct
23 Correct 970 ms 26352 KB Output is correct
24 Correct 892 ms 23008 KB Output is correct
25 Correct 719 ms 20564 KB Output is correct
26 Correct 112 ms 8812 KB Output is correct
27 Correct 115 ms 8792 KB Output is correct
28 Correct 144 ms 9712 KB Output is correct
29 Correct 141 ms 9708 KB Output is correct
30 Correct 114 ms 9068 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 460 ms 14344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 5 ms 3064 KB Output is correct
4 Correct 4 ms 2984 KB Output is correct
5 Correct 5 ms 3064 KB Output is correct
6 Correct 5 ms 3164 KB Output is correct
7 Correct 4 ms 3064 KB Output is correct
8 Correct 4 ms 3064 KB Output is correct
9 Correct 5 ms 3064 KB Output is correct
10 Correct 5 ms 3064 KB Output is correct
11 Correct 5 ms 3064 KB Output is correct
12 Correct 5 ms 3064 KB Output is correct
13 Correct 5 ms 3236 KB Output is correct
14 Correct 6 ms 3064 KB Output is correct
15 Correct 6 ms 3164 KB Output is correct
16 Correct 204 ms 8736 KB Output is correct
17 Correct 1201 ms 26128 KB Output is correct
18 Correct 63 ms 4980 KB Output is correct
19 Correct 189 ms 9808 KB Output is correct
20 Correct 1121 ms 26644 KB Output is correct
21 Correct 233 ms 11480 KB Output is correct
22 Correct 118 ms 7544 KB Output is correct
23 Correct 970 ms 26352 KB Output is correct
24 Correct 892 ms 23008 KB Output is correct
25 Correct 719 ms 20564 KB Output is correct
26 Correct 112 ms 8812 KB Output is correct
27 Correct 115 ms 8792 KB Output is correct
28 Correct 144 ms 9712 KB Output is correct
29 Correct 141 ms 9708 KB Output is correct
30 Correct 114 ms 9068 KB Output is correct
31 Incorrect 5 ms 3064 KB Output isn't correct
32 Halted 0 ms 0 KB -