oj.uz

Submission #649397

# Submission time Handle Problem Language Result Execution time Memory
649397 2022-10-10T07:28:02 Z mychecksedad Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 560 ms 114628 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long int ll;
const int X = 1e6, MOD = 1e9+7;



int n, m;
vector<ll> dp[2];
vector<pair<int, ll>> g[X];
bitset<X> is, vis;

void bfs(int v){
    priority_queue<pair<ll, int>> q;
    for(int i = 0; i < n; ++i) if(is[i]) q.push({0, i}), dp[0][i] = dp[1][i] = 0;
    while(!q.empty()){
        int v = q.top().second; q.pop();
        if(vis[v]) continue;
        vis[v] = 1;
        for(auto k: g[v]){
            int u = k.first, e = k.second;
            if(vis[u]) continue;
            ll d = e + dp[1][v];
            if(dp[0][u] > d){
                dp[1][u] = dp[0][u];
                dp[0][u] = d;
                q.push({-dp[1][u], u});
            }else if(dp[1][u] > d){
                dp[1][u] = d;
                q.push({-dp[1][u], u});
            }
        }
    }
}

int travel_plan(int F, int M, int R[][2], int L[], int K, int P[]){ 
    n = F;
    m = M;
    dp[0].resize(n, MOD);
    dp[1].resize(n, MOD);
    for(int i = 0; i < K; ++i) is[P[i]] = 1;
    for(int i = 0; i < m; ++i){
        g[R[i][0]].pb({R[i][1], L[i]});
        g[R[i][1]].pb({R[i][0], L[i]});
    }
    bfs(0);

    return dp[1][0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23800 KB Output is correct
4 Correct 13 ms 23908 KB Output is correct
5 Correct 13 ms 23884 KB Output is correct
6 Correct 14 ms 23772 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 14 ms 23892 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23800 KB Output is correct
4 Correct 13 ms 23908 KB Output is correct
5 Correct 13 ms 23884 KB Output is correct
6 Correct 14 ms 23772 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 14 ms 23892 KB Output is correct
9 Correct 17 ms 24180 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 14 ms 23892 KB Output is correct
12 Correct 19 ms 24444 KB Output is correct
13 Correct 18 ms 24524 KB Output is correct
14 Correct 14 ms 23764 KB Output is correct
15 Correct 14 ms 23964 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23800 KB Output is correct
4 Correct 13 ms 23908 KB Output is correct
5 Correct 13 ms 23884 KB Output is correct
6 Correct 14 ms 23772 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 14 ms 23892 KB Output is correct
9 Correct 17 ms 24180 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 14 ms 23892 KB Output is correct
12 Correct 19 ms 24444 KB Output is correct
13 Correct 18 ms 24524 KB Output is correct
14 Correct 14 ms 23764 KB Output is correct
15 Correct 14 ms 23964 KB Output is correct
16 Correct 459 ms 106052 KB Output is correct
17 Correct 99 ms 40940 KB Output is correct
18 Correct 125 ms 43380 KB Output is correct
19 Correct 560 ms 114628 KB Output is correct
20 Correct 309 ms 88816 KB Output is correct
21 Correct 55 ms 31472 KB Output is correct
22 Correct 331 ms 85832 KB Output is correct