oj.uz

Submission #1005726

# Submission time Handle Problem Language Result Execution time Memory
1005726 2024-06-22T22:46:25 Z ayankarimova Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 562 ms 91060 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pll pair<ll, ll>
const ll sz=1e5+5, inf=1000000000000000020;
ll c[sz][2LL], used[sz];
vector<pll>g[sz];
priority_queue<pll, vector<pll>, greater<pll>>q;
/*
{} []
*/
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    for(int i=0; i<m; i++){
        ll u=r[i][0], v=r[i][1];
        g[u].push_back({v, l[i]});
        g[v].push_back({u, l[i]});
    }
    for(int i=0; i<n; i++){
        c[i][0]=inf;
        c[i][1]=inf;
    }
    for(int i=0; i<k; i++){
        c[p[i]][0]=0;
        c[p[i]][1]=0;
        q.push({0, p[i]});
    }
    while(q.size()){
        ll u=q.top().second, dis=q.top().first;
        q.pop();
        if(used[u]) continue;
        used[u]=1;
        if(dis>=inf) continue;
        for(auto i:g[u]){
            ll v=i.first, w=i.second;
                if(dis+w<c[v][0]){
                    c[v][1]=c[v][0];
                    c[v][0]=dis+w;
                }
                else c[v][1]=min(c[v][1], dis+w);
                q.push({c[v][1], v});
        }
    }
    return c[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 5 ms 9532 KB Output is correct
13 Correct 4 ms 9564 KB Output is correct
14 Correct 1 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 5 ms 9532 KB Output is correct
13 Correct 4 ms 9564 KB Output is correct
14 Correct 1 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 492 ms 87728 KB Output is correct
17 Correct 77 ms 20684 KB Output is correct
18 Correct 85 ms 22984 KB Output is correct
19 Correct 562 ms 91060 KB Output is correct
20 Correct 366 ms 70932 KB Output is correct
21 Correct 32 ms 13528 KB Output is correct
22 Correct 378 ms 56296 KB Output is correct