oj.uz

Submission #996408

# Submission time Handle Problem Language Result Execution time Memory
996408 2024-06-10T14:47:04 Z phoenix Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 759 ms 68772 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 10;
const ll INF = 1e15;

struct set2 {
    ll val[3];
    set2() {
        val[0] = val[1] = val[2] = INF;
    }
    void insert(ll x) {
        val[2] = x;
        if(val[1] > val[2]) swap(val[1], val[2]);
        if(val[0] > val[1]) swap(val[0], val[1]);
        if(val[1] > val[2]) swap(val[1], val[2]);
    }
};

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


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]].push_back({R[i][1], L[i]});
        g[R[i][1]].push_back({R[i][0], L[i]});
    }
    set<pair<ll, int>> q;
    for(int i = 0; i < k; i++) {
        dp[P[i]].insert(0);
        dp[P[i]].insert(0);
    }
    for(int i = 0; i < n; i++) {
        q.insert({dp[i].val[1], i});
    }
    bool vis[N] = {};
    while(!q.empty()) {
        int s = q.begin()->second;
        if(dp[s].val[1] == INF) break;
        q.erase(q.begin());
        vis[s] = 1;
        for(auto [to, w] : g[s]) {
            if(vis[to]) continue;
            q.erase({dp[to].val[1], to});
            dp[to].insert(dp[s].val[1] + w);
            q.insert({dp[to].val[1], to});
        }
    }
    return dp[0].val[1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8828 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 2 ms 8792 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 9052 KB Output is correct
13 Correct 3 ms 9332 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 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8828 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 2 ms 8792 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 9052 KB Output is correct
13 Correct 3 ms 9332 KB Output is correct
14 Correct 1 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 661 ms 62420 KB Output is correct
17 Correct 82 ms 24912 KB Output is correct
18 Correct 124 ms 26448 KB Output is correct
19 Correct 759 ms 68772 KB Output is correct
20 Correct 269 ms 56276 KB Output is correct
21 Correct 51 ms 14504 KB Output is correct
22 Correct 329 ms 53476 KB Output is correct