oj.uz

Submission #1005725

# Submission time Handle Problem Language Result Execution time Memory
1005725 2024-06-22T22:45:34 Z ayankarimova Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 393 ms 105236 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(!used[v]){
                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 8820 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 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 2 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 8820 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 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 2 ms 8796 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 1 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 4 ms 9564 KB Output is correct
13 Correct 4 ms 9564 KB Output is correct
14 Correct 2 ms 9048 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 8820 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 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 2 ms 8796 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 1 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 4 ms 9564 KB Output is correct
13 Correct 4 ms 9564 KB Output is correct
14 Correct 2 ms 9048 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 376 ms 103600 KB Output is correct
17 Correct 55 ms 24000 KB Output is correct
18 Correct 70 ms 26308 KB Output is correct
19 Correct 393 ms 105236 KB Output is correct
20 Correct 281 ms 82896 KB Output is correct
21 Correct 39 ms 14928 KB Output is correct
22 Correct 270 ms 69116 KB Output is correct