Submission #425755

#	Time	Username	Problem	Language	Result	Execution time	Memory
425755		temurbek_khujaev	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1707 ms	60108 KiB

crocodile

#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 (stderr)

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 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11