oj.uz

Submission #690587

# Submission time Handle Problem Language Result Execution time Memory
690587 2023-01-30T10:16:24 Z saayan007 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 492 ms 89252 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

#warning evth is integer
using ll = long long;
using pl = pair<long long, long long>;
using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<long long>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<long long, long long>>;

#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define fr first 
#define sc second
#define mp make_pair
#define pb emplace_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

const ll mxN = 1e5 + 1;
const ll inf = INT_MAX;
vpl adj[mxN];
ll ans[mxN];


int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    fur(i, 0, M - 1) {
        ll a = R[i][0], b = R[i][1], wt = L[i];
        adj[a].pb(b, wt);
        adj[b].pb(a, wt);
    }

    priority_queue<pl> pq;
    ll mn[mxN];
    ll sm[mxN];
    fur(i, 0, N - 1) {
        mn[i] = sm[i] = -1;
    }
    fur(i, 0, K - 1) {
        mn[P[i]] = sm[P[i]] = 0;
        pq.emplace(-mn[P[i]], P[i]);
    }
    bool proc[mxN] = {};

    while(!pq.empty()) {
        ll a = pq.top().sc;
        pq.pop();
        if(proc[a] || sm[a] == -1) {
            continue;
        }
        proc[a] = 1;

        for(auto [b, wt] : adj[a]) {
            if(sm[a] + wt < mn[b] || mn[b] == -1) {
                if(mn[b] != -1) {
                    sm[b] = mn[b];
                    pq.emplace(-sm[b], b);
                }
                mn[b] = sm[a] + wt;
            } else if(sm[a] + wt < sm[b] || sm[b] == -1) {
                sm[b] = sm[a] + wt;
                pq.emplace(-sm[b], b);
            }
        }
    }

    return (int)sm[0];
}

Compilation message

crocodile.cpp:5:2: warning: #warning evth is integer [-Wcpp]
    5 | #warning evth is integer
      |  ^~~~~~~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 4 ms 4340 KB Output is correct
5 Correct 3 ms 4332 KB Output is correct
6 Correct 3 ms 4308 KB Output is correct
7 Correct 3 ms 4340 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 4 ms 4692 KB Output is correct
10 Correct 2 ms 4308 KB Output is correct
11 Correct 3 ms 4436 KB Output is correct
12 Correct 5 ms 4980 KB Output is correct
13 Correct 5 ms 5104 KB Output is correct
14 Correct 3 ms 4328 KB Output is correct
15 Correct 3 ms 4436 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 4 ms 4340 KB Output is correct
5 Correct 3 ms 4332 KB Output is correct
6 Correct 3 ms 4308 KB Output is correct
7 Correct 3 ms 4340 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 4 ms 4692 KB Output is correct
10 Correct 2 ms 4308 KB Output is correct
11 Correct 3 ms 4436 KB Output is correct
12 Correct 5 ms 4980 KB Output is correct
13 Correct 5 ms 5104 KB Output is correct
14 Correct 3 ms 4328 KB Output is correct
15 Correct 3 ms 4436 KB Output is correct
16 Correct 418 ms 74772 KB Output is correct
17 Correct 88 ms 17740 KB Output is correct
18 Correct 117 ms 20116 KB Output is correct
19 Correct 492 ms 89252 KB Output is correct
20 Correct 295 ms 69648 KB Output is correct
21 Correct 35 ms 10904 KB Output is correct
22 Correct 272 ms 65228 KB Output is correct