oj.uz

Submission #148275

# Submission time Handle Problem Language Result Execution time Memory
148275 2019-08-31T19:39:30 Z karma Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 723 ms 55520 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 int oo = int(1e9) + 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 2684 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 2808 KB Output is correct
7 Correct 5 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 2684 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 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 3064 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 8 ms 3064 KB Output is correct
13 Correct 7 ms 3064 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2780 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 2684 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 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 3064 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 8 ms 3064 KB Output is correct
13 Correct 7 ms 3064 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2780 KB Output is correct
16 Correct 675 ms 48432 KB Output is correct
17 Correct 128 ms 15156 KB Output is correct
18 Correct 155 ms 16152 KB Output is correct
19 Correct 723 ms 55520 KB Output is correct
20 Correct 333 ms 39120 KB Output is correct
21 Correct 56 ms 7672 KB Output is correct
22 Incorrect 384 ms 37936 KB Output isn't correct