oj.uz

Submission #1005727

# Submission time Handle Problem Language Result Execution time Memory
1005727 2024-06-22T22:47:45 Z vjudge1 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 522 ms 99420 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 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8824 KB Output is correct
4 Correct 1 ms 8792 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 2 ms 8832 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 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8824 KB Output is correct
4 Correct 1 ms 8792 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 2 ms 8832 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 9604 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 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8824 KB Output is correct
4 Correct 1 ms 8792 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 2 ms 8832 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 9604 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 482 ms 95920 KB Output is correct
17 Correct 79 ms 22468 KB Output is correct
18 Correct 83 ms 25032 KB Output is correct
19 Correct 522 ms 99420 KB Output is correct
20 Correct 344 ms 77596 KB Output is correct
21 Correct 35 ms 14540 KB Output is correct
22 Correct 326 ms 63692 KB Output is correct