oj.uz

Submission #425902

# Submission time Handle Problem Language Result Execution time Memory
425902 2021-06-13T12:17:20 Z dxz05 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 839 ms 53288 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MP make_pair

const ll INF = 1e18 + 1e8;
const int N = 3e5 + 3e2;

vector<pair<int, int>> g[N];

ll dp[N];
bool processed[N];
int cnt[N];

pair<ll, ll> p[N]; /// p[i].first <= p[i].second

void upd(int i, ll x){
    vector<ll> v = {p[i].first, p[i].second, x};
    sort(v.begin(), v.end());
    p[i].first = v[0];
    p[i].second = v[1];
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    for (int i = 0; i < M; i++){
        g[R[i][0]].emplace_back(R[i][1], L[i]);
        g[R[i][1]].emplace_back(R[i][0], L[i]);
    }

    for (int i = 0; i < N; i++){
        p[i] = MP(INF, INF);
        dp[i] = INF;
    }

    priority_queue<pair<ll, int>> pq;
    for (int i = 0; i < K; i++){
        dp[P[i]] = 0;
        pq.push(MP(0, P[i]));
        p[P[i]] = MP(0, 0);
    }

    while (!pq.empty()){
        int v = pq.top().second; pq.pop();
        if (processed[v]) continue;
        processed[v] = true;

        for (auto edge : g[v]){
            int u = edge.first, w = edge.second;

            upd(u, dp[v] + w);
            if (dp[u] > p[u].second){
                dp[u] = p[u].second;
                pq.push(MP(-dp[u], u));
            }
        }

    }

    //for (int i = 0; i < N; i++) cout << dp[i] << ' ';

    return dp[0];
}

/**
5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14
*/

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 8 ms 7372 KB Output is correct
6 Correct 6 ms 7372 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 7 ms 7372 KB Output is correct
9 Correct 6 ms 7528 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 7 ms 7372 KB Output is correct
12 Correct 10 ms 7756 KB Output is correct
13 Correct 9 ms 7756 KB Output is correct
14 Correct 7 ms 7372 KB Output is correct
15 Correct 8 ms 7372 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 8 ms 7372 KB Output is correct
6 Correct 6 ms 7372 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 7 ms 7372 KB Output is correct
9 Correct 6 ms 7528 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 7 ms 7372 KB Output is correct
12 Correct 10 ms 7756 KB Output is correct
13 Correct 9 ms 7756 KB Output is correct
14 Correct 7 ms 7372 KB Output is correct
15 Correct 8 ms 7372 KB Output is correct
16 Correct 628 ms 47560 KB Output is correct
17 Correct 102 ms 16856 KB Output is correct
18 Correct 132 ms 18196 KB Output is correct
19 Correct 839 ms 53288 KB Output is correct
20 Correct 448 ms 41284 KB Output is correct
21 Correct 54 ms 11540 KB Output is correct
22 Correct 459 ms 37040 KB Output is correct