oj.uz

Submission #958193

# Submission time Handle Problem Language Result Execution time Memory
958193 2024-04-05T06:19:28 Z daoda Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 684 ms 75956 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(x, a, b) for(int x=a;x < int(b); x++)
#define endl '\n'
#define TESTCASE ll t; cin >> t; for(ll T=0; T < t; T++)

using namespace std;
// using namespace __gnu_pbds;

// typedef tree<int,null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update> Indexed_set;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long double ld;

const int INF = 1e9;
const ll INIT = 7;
const ll MAX_VAL = (ll) 1e9;
const ll MAX_SZ = (ll) 2e5;
const long double eps = 1e-4;
const int MOD = 998244353;

vi rd = {0, 1 , 0, -1}, cd = {1, 0, -1, 0};

const int MAX_DIST = int(1e9);

int travel_plan(int n, int m, int r[][2], int* l, int k, int* p) {
    vector<vpi> adj(n);

    FOR(i, 0, m) {
        int f = r[i][0], s = r[i][1];

        adj[f].push_back(make_pair(l[i], s));
        adj[s].push_back(make_pair(l[i], f));
    }

    vi ans(n, -2);

    priority_queue<pi, vpi, greater<pi>> tr;

    FOR(i, 0, k) {
        tr.push(make_pair(0, p[i]));
        ans[p[i]] = -1;
    }

    while(!tr.empty()) {
        auto [dist, chamber] = tr.top();
        tr.pop();

        if(ans[chamber] == -2) {
            ans[chamber]++;
            continue;
        }

        if(ans[chamber] >= 0 || dist > MAX_DIST) continue;

        ans[chamber] = dist;

        for(auto next : adj[chamber]) {
            tr.push(make_pair(dist + next.first, next.second));
        }
    }

    // FOR(i, 0, n) cout << ans[i] << " ";
    // cout << endl;

    return ans[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 4 ms 4956 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 5 ms 5168 KB Output is correct
13 Correct 7 ms 5208 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 4 ms 4956 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 5 ms 5168 KB Output is correct
13 Correct 7 ms 5208 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 581 ms 72628 KB Output is correct
17 Correct 62 ms 15144 KB Output is correct
18 Correct 85 ms 16420 KB Output is correct
19 Correct 684 ms 75956 KB Output is correct
20 Correct 474 ms 65720 KB Output is correct
21 Correct 33 ms 8856 KB Output is correct
22 Correct 414 ms 46752 KB Output is correct