oj.uz

Submission #115160

# Submission time Handle Problem Language Result Execution time Memory
115160 2019-06-05T13:46:09 Z songc Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 8 ms 3456 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;

int N, M;
vector<pii> G[101010];
set<pii> U;
LL 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++) {
        chk[p[i]] = true;
        for (pii v : G[p[i]]){
            if (!F[v.first] || F[v.first] > v.second) {
                U.erase(pii(S[v.first], v.first));
                S[v.first] = F[v.first], F[v.first] = v.second;
                if (S[v.first]) U.insert(pii(S[v.first], v.first));
            }
            else if (!S[v.first] || S[v.first] > v.second) {
                U.erase(pii(S[v.first], v.first));
                S[v.first] = v.second;
                U.insert(pii(S[v.first], v.first));
            }
        }
    }
    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 4 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct

Subtask #2
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 4 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 8 ms 3328 KB Output is correct
13 Correct 7 ms 3456 KB Output is correct
14 Correct 5 ms 2816 KB Output is correct
15 Incorrect 5 ms 2816 KB Output isn't correct

Subtask #3
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 4 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 8 ms 3328 KB Output is correct
13 Correct 7 ms 3456 KB Output is correct
14 Correct 5 ms 2816 KB Output is correct
15 Incorrect 5 ms 2816 KB Output isn't correct