oj.uz

Submission #115166

# Submission time Handle Problem Language Result Execution time Memory
115166 2019-06-05T14:44:28 Z songc Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1027 ms 60132 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, M;
vector<pii> G[101010];
set<pii> U;
int F[101010], S[101010];
bool chk[101010];

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++){
        G[r[i][0]].push_back(pii(r[i][1], l[i]));
        G[r[i][1]].push_back(pii(r[i][0], l[i]));
    }
    for (int i=0; i<k; i++){
        U.insert(pii(0, p[i]));
        chk[p[i]]=true;
    }
    while(!U.empty()){
        int u=U.begin()->second;
        U.erase(U.begin());
        chk[u] = true;
        for (pii v : G[u]){
            if (chk[v.first]) continue;
            if (!F[v.first] || F[v.first] > v.second+S[u]){
                U.erase(pii(S[v.first], v.first));
                S[v.first] = F[v.first], F[v.first] = v.second+S[u];
                if (S[v.first]) U.insert(pii(S[v.first], v.first));
            }
            else if (!S[v.first] || S[v.first] > v.second+S[u]){
                U.erase(pii(S[v.first], v.first));
                S[v.first] = v.second+S[u];
                U.insert(pii(S[v.first], v.first));
            }
        }
    }
    return S[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 5 ms 2944 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 5 ms 2816 KB Output is correct
9 Correct 6 ms 2944 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 7 ms 3072 KB Output is correct
13 Correct 6 ms 3072 KB Output is correct
14 Correct 4 ms 2816 KB Output is correct
15 Correct 4 ms 2816 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 5 ms 2944 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 5 ms 2816 KB Output is correct
9 Correct 6 ms 2944 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 7 ms 3072 KB Output is correct
13 Correct 6 ms 3072 KB Output is correct
14 Correct 4 ms 2816 KB Output is correct
15 Correct 4 ms 2816 KB Output is correct
16 Correct 718 ms 40176 KB Output is correct
17 Correct 93 ms 13944 KB Output is correct
18 Correct 128 ms 15464 KB Output is correct
19 Correct 1027 ms 60132 KB Output is correct
20 Correct 328 ms 49692 KB Output is correct
21 Correct 45 ms 7800 KB Output is correct
22 Correct 354 ms 46072 KB Output is correct