oj.uz

Submission #72588

# Submission time Handle Problem Language Result Execution time Memory
72588 2018-08-26T10:30:51 Z Bruteforceman Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 1284 ms 104408 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
const long long inf = 1e15;

struct data {
    int node;
    long long dist;
    data (int node, long long dist) {
        this -> node = node;
        this -> dist = dist;
    }
    data ( ) {}
    bool operator < (data x) const {
        return dist > x.dist;
    }
};

vector <int> g[100010];
vector <int> c[100010];
long long d[100010][2];
bool vis[100010];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    // freopen("in.txt", "r", stdin);

    int n, m, k;
    n = N;
    m = M;
    k = K;
    for(int i = 0; i < m; i++) {
        int p = R[i][0], q = R[i][1], r = L[i];
        g[p].push_back(q);
        g[q].push_back(p);
        c[p].push_back(r);
        c[q].push_back(r);
    }
    for(int i = 0; i < n; i++) {
        d[i][0] = d[i][1] = inf;
    }

    priority_queue <data> Q;
    for(int i = 0; i < k; i++) {
        int x = P[i];
        d[x][1] = d[x][0] = 0;
        Q.push(data(x, 0));
    }
    while(not Q.empty()) {
        data x = Q.top();
        Q.pop();
        int p = x.node;
        long long dist = x.dist;
        if(vis[p] == true) continue;

        vis[p] = true;
        for(unsigned i = 0; i < g[p].size(); i++) {
            long long cost = c[p][i] + dist;
            int q = g[p][i];

            if(d[q][0] >= cost) {
                d[q][1] = d[q][0];
                d[q][0] = cost;
                Q.push( data(q, d[q][1]) );
            } else if (d[q][1] > cost) {
                d[q][1] = cost;
                Q.push( data(q, cost) );
            }
        }
    }
  	if(d[0][1] == inf) d[0][1] = -1;
    return d[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 6 ms 5092 KB Output is correct
3 Correct 7 ms 5204 KB Output is correct
4 Correct 8 ms 5468 KB Output is correct
5 Correct 9 ms 5468 KB Output is correct
6 Correct 7 ms 5468 KB Output is correct
7 Correct 6 ms 5524 KB Output is correct
8 Correct 8 ms 5588 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 6 ms 5092 KB Output is correct
3 Correct 7 ms 5204 KB Output is correct
4 Correct 8 ms 5468 KB Output is correct
5 Correct 9 ms 5468 KB Output is correct
6 Correct 7 ms 5468 KB Output is correct
7 Correct 6 ms 5524 KB Output is correct
8 Correct 8 ms 5588 KB Output is correct
9 Correct 10 ms 5800 KB Output is correct
10 Correct 8 ms 5800 KB Output is correct
11 Correct 8 ms 5800 KB Output is correct
12 Correct 10 ms 6048 KB Output is correct
13 Correct 10 ms 6144 KB Output is correct
14 Correct 7 ms 6144 KB Output is correct
15 Correct 10 ms 6144 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 6 ms 5092 KB Output is correct
3 Correct 7 ms 5204 KB Output is correct
4 Correct 8 ms 5468 KB Output is correct
5 Correct 9 ms 5468 KB Output is correct
6 Correct 7 ms 5468 KB Output is correct
7 Correct 6 ms 5524 KB Output is correct
8 Correct 8 ms 5588 KB Output is correct
9 Correct 10 ms 5800 KB Output is correct
10 Correct 8 ms 5800 KB Output is correct
11 Correct 8 ms 5800 KB Output is correct
12 Correct 10 ms 6048 KB Output is correct
13 Correct 10 ms 6144 KB Output is correct
14 Correct 7 ms 6144 KB Output is correct
15 Correct 10 ms 6144 KB Output is correct
16 Correct 1095 ms 63800 KB Output is correct
17 Correct 128 ms 63800 KB Output is correct
18 Correct 192 ms 63800 KB Output is correct
19 Correct 1284 ms 95700 KB Output is correct
20 Correct 391 ms 95700 KB Output is correct
21 Correct 74 ms 95700 KB Output is correct
22 Correct 636 ms 104408 KB Output is correct