oj.uz

Submission #425755

# Submission time Handle Problem Language Result Execution time Memory
425755 2021-06-13T11:03:07 Z temurbek_khujaev Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1707 ms 60108 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wc++17-extensions"
using namespace std;
#define N 100100
vector<pair<int, int> > g[N];
bool deleted[N];
int opt[N][2];
long long INF = 1e9+404;
int ind[N][2];
bool is_exit[N];
set<pair<int, int> > s;

void upd(int v, int val) {
    s.erase({opt[v][1], v});
    if (opt[v][0] > val || opt[v][0] == val && opt[v][1] > val) {

        opt[v][1] = opt[v][0];
        opt[v][0] = val;
    } else {
        if (opt[v][1] > val) {
            opt[v][1] = val;
        }
    }
    s.insert({opt[v][1], v});
}

void del(int v) {

    deleted[v] = true;
    s.erase({opt[v][1], v});
    for (auto[x, w]:g[v]) {
        if (!deleted[x]) upd(x, opt[v][1] + w);
    }
}

int travel_plan(int n, int M, int R[][2], int L[], int K, int P[]) {
    for (int i = 0; i < n; i++) {
        opt[i][0] = opt[i][1] = INF;
    }
    for (int i = 0; i < M; i++) {
        g[R[i][0]].emplace_back(R[i][1], L[i]);
        g[R[i][1]].emplace_back(R[i][0], L[i]);
    }
    for (int i = 0; i < K; i++) {
        deleted[P[i]] = true;
    }
    for (int i = 0; i < K; i++) {
        int v = P[i];
        opt[v][1] = 0;
        del(v);
    }
    while (!s.empty()) {
        del(s.begin()->second);
    }
//    for (int i = 0; i < n; i++) {
//        cerr <<i << ' ' << opt[i][0] << ' ' << opt[i][1] << endl;
//    }
    return opt[0][1];
}


#pragma clang diagnostic pop

Compilation message

crocodile.cpp:4: warning: ignoring '#pragma clang diagnostic' [-Wunknown-pragmas]
    4 | #pragma clang diagnostic push
      | 
crocodile.cpp:5: warning: ignoring '#pragma clang diagnostic' [-Wunknown-pragmas]
    5 | #pragma clang diagnostic ignored "-Wc++17-extensions"
      | 
crocodile.cpp:65: warning: ignoring '#pragma clang diagnostic' [-Wunknown-pragmas]
   65 | #pragma clang diagnostic pop
      | 
crocodile.cpp: In function 'void upd(int, int)':
crocodile.cpp:18:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   18 |     if (opt[v][0] > val || opt[v][0] == val && opt[v][1] > val) {
      |                            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 5 ms 2892 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 4 ms 2764 KB Output is correct
12 Correct 8 ms 3148 KB Output is correct
13 Correct 6 ms 3148 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 5 ms 2892 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 4 ms 2764 KB Output is correct
12 Correct 8 ms 3148 KB Output is correct
13 Correct 6 ms 3148 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct
16 Correct 1186 ms 56212 KB Output is correct
17 Correct 91 ms 13800 KB Output is correct
18 Correct 166 ms 15308 KB Output is correct
19 Correct 1707 ms 60108 KB Output is correct
20 Correct 489 ms 49636 KB Output is correct
21 Correct 53 ms 7720 KB Output is correct
22 Correct 519 ms 46072 KB Output is correct