oj.uz

Submission #722033

# Submission time Handle Problem Language Result Execution time Memory
722033 2023-04-11T10:45:18 Z Zflop Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 476 ms 49984 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define all(x) x.begin(), x.end()
using namespace std;
 
template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
 
const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e17 + 69;
 
int n, m, r[maxn][2], l[maxn], k, p[maxn];
pair<ll, ll> f[maxn];
vector<pa> g[maxn];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]);
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
    priority_queue<pall, vector<pall>, greater<pall>> q;
    fill_n(f, n, make_pair(oo, oo));
    for(int i = 0; i < k; i++) {
        f[p[i]] = {0, 0};
        q.push({0, p[i]});
    }
 
    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]});
    }
 
    while(!q.empty()) {
        int u = q.top().se;
        ll fu = q.top().fi;
        q.pop();
 
        if(fu != f[u].se) continue;
        for(auto e:g[u]) {
            int v = e.fi, w = e.se;
            if(f[v].fi > fu + w) {
                if(f[v].se != f[v].fi && f[v].fi < oo) q.push({f[v].fi, v});
                f[v].se = f[v].fi;
                f[v].fi = fu + w;
            } else if(f[v].se > fu + w) {
                f[v].se = fu + w;
                q.push({f[v].se, v});
            }
        }
    }
    return f[0].se;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 4 ms 5016 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 6 ms 5076 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 5 ms 5460 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 4 ms 5076 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 4 ms 5016 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 6 ms 5076 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 5 ms 5460 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 4 ms 5076 KB Output is correct
16 Correct 389 ms 44856 KB Output is correct
17 Correct 77 ms 13528 KB Output is correct
18 Correct 90 ms 14980 KB Output is correct
19 Correct 476 ms 49984 KB Output is correct
20 Correct 273 ms 38584 KB Output is correct
21 Correct 33 ms 8832 KB Output is correct
22 Correct 267 ms 34344 KB Output is correct