oj.uz

Submission #148284

# Submission time Handle Problem Language Result Execution time Memory
148284 2019-08-31T19:59:30 Z karma Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 641 ms 37696 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
#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<int, int> pii;

pii top;
int8_t vis[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;
    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) vis[p[i]] = 1, pq.push(mp(0, p[i]));
    int v;
    while(!pq.empty()) {
        top = pq.top(); pq.pop();
        if(!vis[top.se]) ++vis[top.se];
        else if(vis[top.se] == 1) {
            if(!top.se) return top.fi;
            ++vis[top.se];
            for(int i: a[top.se]) {
               v = r[i][0] ^ r[i][1] ^ top.se;
               if(vis[v] < 2) pq.push(mp(top.fi + l[i], v));
            }
        }
    }
}

//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);
//}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2680 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 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2680 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 2808 KB Output is correct
12 Correct 9 ms 3064 KB Output is correct
13 Correct 7 ms 2936 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2680 KB Output is correct

Subtask #3
11.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 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2680 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 2808 KB Output is correct
12 Correct 9 ms 3064 KB Output is correct
13 Correct 7 ms 2936 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2680 KB Output is correct
16 Correct 622 ms 35924 KB Output is correct
17 Correct 96 ms 8184 KB Output is correct
18 Correct 115 ms 9080 KB Output is correct
19 Correct 641 ms 37696 KB Output is correct
20 Correct 313 ms 25848 KB Output is correct
21 Correct 50 ms 5240 KB Output is correct
22 Correct 499 ms 23176 KB Output is correct