oj.uz

Submission #892536

# Submission time Handle Problem Language Result Execution time Memory
892536 2023-12-25T13:21:30 Z TahirAliyev Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 630 ms 88120 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define oo 1e18

const int MAX = 1e5 + 5;
int n, m;

vector<int> esc;

vector<pii> g[MAX];

ll dp[MAX][2];

void djikstra(){
    for(int i = 0; i < n; i++){
        dp[i][0] = oo;
        dp[i][1] = oo;
    }
    set<pii> s;
    for(int e : esc){
        dp[e][0] = 0;
        dp[e][1] = 0;
        s.insert({0, e});
    }
    while(s.size()){
        int a = s.begin()->second;
        s.erase(s.begin());
        for(pii to : g[a]){
            ll nw = dp[a][1] + to.second;
            if(dp[to.first][0] <= nw){
                if(dp[to.first][1] > nw){
                    s.erase({dp[to.first][1], to.first});
                    dp[to.first][1] = nw;
                    s.insert({dp[to.first][1], to.first});
                }
            }
            else{
                s.erase({dp[to.first][1], to.first});
                dp[to.first][1] = dp[to.first][0];
                s.insert({dp[to.first][1], to.first});
                dp[to.first][0] = nw;
            }
        }
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N, m = M;
    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 < K; i++){
        esc.push_back(P[i]);
    }
    djikstra();
    return dp[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 8968 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 7000 KB Output is correct
12 Correct 4 ms 9052 KB Output is correct
13 Correct 4 ms 9560 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 8968 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 7000 KB Output is correct
12 Correct 4 ms 9052 KB Output is correct
13 Correct 4 ms 9560 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct
16 Correct 402 ms 84660 KB Output is correct
17 Correct 60 ms 21872 KB Output is correct
18 Correct 113 ms 24148 KB Output is correct
19 Correct 630 ms 88120 KB Output is correct
20 Correct 231 ms 72796 KB Output is correct
21 Correct 34 ms 16220 KB Output is correct
22 Correct 252 ms 69204 KB Output is correct