oj.uz

Submission #876710

# Submission time Handle Problem Language Result Execution time Memory
876710 2023-11-22T08:48:58 Z deadeye0 Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 414 ms 88080 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define si second
#define ar array
#define pb push_back
typedef pair<ll,ll> pi;
typedef tuple<int,int,int> ti;  
typedef vector<int> vi;
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 100010;
int n, m;
ll d1[MAXN], d2[MAXN];
vector<vector<pi>> g;
priority_queue<pi, vector<pi>, greater<pi>> pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) 
{
    n = N, m = M;
    g.resize(n);
    for (int i = 0; i < m; ++i) {
        int u = R[i][0], v = R[i][1];
        g[u].pb({v, L[i]});
        g[v].pb({u, L[i]});
    }
    memset(d1, -1, sizeof d1);
    memset(d2, -1, sizeof d2);
    for (int i = 0; i < K; ++i)  {
        d1[P[i]] = 0;
        d2[P[i]] = 0;
        pq.push({0, P[i]});
    }   
    while (pq.size()) {
        auto [d, x] = pq.top(); pq.pop();
        if (d2[x] != d) continue;
        for (auto i: g[x]) {
            ll val = d + i.si;
            if (d1[i.fi] == -1) {
                d1[i.fi] = val;
            } else if (val < d1[i.fi] && d1[i.fi] != d2[i.fi]) {
                swap(d1[i.fi], d2[i.fi]);
                d1[i.fi] = val;
                pq.push({d2[i.fi], i.fi});
            } else if (d2[i.fi] == -1 || d2[i.fi] > val) {
                d2[i.fi] = val;
                pq.push({val, i.fi});
            }
        }
    }
    return d2[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6572 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6844 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 1 ms 6852 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6572 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6844 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 1 ms 6852 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 1 ms 6572 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 5 ms 7260 KB Output is correct
13 Correct 5 ms 7448 KB Output is correct
14 Correct 2 ms 6744 KB Output is correct
15 Correct 2 ms 6744 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6572 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6844 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 1 ms 6852 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 1 ms 6572 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 5 ms 7260 KB Output is correct
13 Correct 5 ms 7448 KB Output is correct
14 Correct 2 ms 6744 KB Output is correct
15 Correct 2 ms 6744 KB Output is correct
16 Correct 347 ms 79812 KB Output is correct
17 Correct 54 ms 22616 KB Output is correct
18 Correct 69 ms 25168 KB Output is correct
19 Correct 414 ms 88080 KB Output is correct
20 Correct 226 ms 66208 KB Output is correct
21 Correct 28 ms 14516 KB Output is correct
22 Incorrect 258 ms 63312 KB Output isn't correct
23 Halted 0 ms 0 KB -