oj.uz

Submission #148277

# Submission time Handle Problem Language Result Execution time Memory
148277 2019-08-31T19:42:04 Z karma Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 748 ms 39312 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
#define ll      long long
#define pb      emplace_back
#define mp      make_pair
#define fi      first
#define se      second

using namespace std;

const int N = int(1e5) + 2;
const ll oo = (ll)(1e15) + 7;
typedef pair<ll, ll> pii;

pii top, d[N];
vector<int> a[N];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    fill(d, d + n, mp(oo, oo));
    for(int i = 0; i < m; ++i) a[r[i][0]].pb(i), a[r[i][1]].pb(i);
    for(int i = 0; i < k; ++i) d[p[i]] = mp(0, 0), pq.push(mp(0, p[i]));
    ll v, dis;
    while(!pq.empty()) {
        top = pq.top(); pq.pop();
        if(d[top.se].se != top.fi) continue;
        for(int i: a[top.se]) {
            v = top.se ^ r[i][0] ^ r[i][1];
            dis = d[top.se].se + l[i];
            if(d[v].fi > dis) d[v] = mp(dis, d[v].fi);
            else if(d[v].se > dis) d[v] = mp(d[v].fi, dis);
            else continue;
            pq.push(mp(d[v].se, v));
        }
    }
    return d[0].se;
}
//
//int n, m, r[N][2], l[N], k, p[N];
//
//int main()
//{
//    ios_base::sync_with_stdio(0);
//    cin.tie(0), cout.tie(0);
//    if(fopen("test.inp", "r")) {
//        freopen("test.inp", "r", stdin);
//        freopen("test.out", "w", stdout);
//    }
//    cin >> n >> m >> k;
//    for(int i = 0; i < m; ++i) cin >> r[i][0] >> r[i][1] >> l[i];
//    for(int i = 0; i < k; ++i) cin >> p[i];
//    cout << travel_plan(n, m, r, l, k, p);
//}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 4 ms 2812 KB Output is correct
7 Correct 4 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 2808 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2744 KB Output is correct
12 Correct 8 ms 2940 KB Output is correct
13 Correct 7 ms 2936 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 4 ms 2680 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 4 ms 2812 KB Output is correct
7 Correct 4 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 2808 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2744 KB Output is correct
12 Correct 8 ms 2940 KB Output is correct
13 Correct 7 ms 2936 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 4 ms 2680 KB Output is correct
16 Correct 590 ms 32368 KB Output is correct
17 Correct 121 ms 11888 KB Output is correct
18 Correct 150 ms 12776 KB Output is correct
19 Correct 748 ms 39312 KB Output is correct
20 Correct 345 ms 26048 KB Output is correct
21 Correct 55 ms 6264 KB Output is correct
22 Incorrect 382 ms 23812 KB Output isn't correct