oj.uz

Submission #17010

# Submission time Handle Problem Language Result Execution time Memory
17010 2015-11-03T19:04:04 Z erdemkiraz Crocodile's Underground City (IOI11_crocodile) C++
100 / 100
 660 ms 153068 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 1e5 + 5;

int n, m;
int a[N], mn[N], mn2[N];
vector < ii > v[N];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n = N;
    m = M;
    for(int i = 0; i < m; i++) {
        int x = R[i][0] + 1;
        int y = R[i][1] + 1;
        int c = L[i];
        v[x].push_back(ii(y, c));
        v[y].push_back(ii(x, c));
    }
    priority_queue < ii > Q;
    memset(mn, 63, sizeof(mn));
    memset(mn2, 63, sizeof(mn2));
    for(int i = 0; i < K; i++) {
        int x = P[i] + 1;
        a[x] = 1;
        Q.push(ii(0, x));
        mn[x] = mn2[x] = 0;
    }
    while(!Q.empty()) {
        int c = -Q.top().first;
        int x = Q.top().second;
        Q.pop();
        if(c > mn2[x])
            continue;
        foreach(it, v[x]) {
            int u = it -> first;
            int e = it -> second;
            int cur = mn2[u];
            if(c + e < mn[u]) {
                mn2[u] = mn[u];
                mn[u] = c + e;
            }
            else
                mn2[u] = min(mn2[u], c + e);
            if(cur != mn2[u]) {
                Q.push(ii(-mn2[u], u));
            }
        }
    }
    return mn2[1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 122752 KB Output is correct
2 Correct 0 ms 122620 KB Output is correct
3 Correct 2 ms 122620 KB Output is correct
4 Correct 6 ms 122752 KB Output is correct
5 Correct 0 ms 122884 KB Output is correct
6 Correct 0 ms 122620 KB Output is correct
7 Correct 0 ms 122620 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 149212 KB Output is correct
2 Correct 68 ms 127240 KB Output is correct
3 Correct 45 ms 128428 KB Output is correct
4 Correct 660 ms 153068 KB Output is correct
5 Correct 291 ms 145508 KB Output is correct
6 Correct 20 ms 124864 KB Output is correct
7 Correct 402 ms 140964 KB Output is correct