oj.uz

Submission #531005

# Submission time Handle Problem Language Result Execution time Memory
531005 2022-02-27T10:13:33 Z mat50013 Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 458 ms 51812 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MAX_N(100005);
vector<pair<int, int> > G[MAX_N + 5];
ll distF[MAX_N + 5], distS[MAX_N + 5];
bool viz[MAX_N + 5];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i = 0; i < M; ++i)
        G[R[i][0]].push_back({R[i][1], L[i]}), G[R[i][1]].push_back({R[i][0], L[i]});
    for(int i = 0; i < N; ++i)
        distF[i] = 1e9 + 5, distS[i] = 1e9 + 5;
    priority_queue<pair<ll, int>, vector<pair<ll, int> > , greater<pair<ll, int> > > q;
    for(int i = 0; i < K; ++i)
    {
        distF[P[i]] = distS[P[i]] = 0;
        q.push({0, P[i]});
    }
    while(!q.empty())
    {
        int nd = q.top().second;
        ll dist = q.top().first;
        q.pop();
        if(viz[nd])
            continue;
        viz[nd] = 1;
        for(auto it: G[nd])
            if(distF[it.first] == 1e9 + 5)
            {
                distF[it.first] = dist + it.second;
                q.push({distS[it.first], it.first});
            }
            else if(distS[it.first] == 1e9 + 5 || dist + it.second < distS[it.first]){
                distS[it.first] = dist + it.second;
                if(distF[it.first] > distS[it.first])
                    swap(distF[it.first], distS[it.first]);
                q.push({distS[it.first], it.first});
            }
    }
    return distS[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 4 ms 3020 KB Output is correct
13 Correct 4 ms 3020 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 4 ms 3020 KB Output is correct
13 Correct 4 ms 3020 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct
16 Correct 372 ms 44632 KB Output is correct
17 Correct 85 ms 13464 KB Output is correct
18 Correct 96 ms 14792 KB Output is correct
19 Correct 458 ms 51812 KB Output is correct
20 Correct 230 ms 36592 KB Output is correct
21 Correct 35 ms 7164 KB Output is correct
22 Correct 250 ms 32556 KB Output is correct