oj.uz

Submission #1094207

# Submission time Handle Problem Language Result Execution time Memory
1094207 2024-09-29T02:09:23 Z anhthi Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 363 ms 64460 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)

template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }

template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }

template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a));
        a.resize(unique(all(a)) - a.begin());
    }

int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
    return l + abs((ll) rng()) % (r - l + 1);
}

const ll oo = (ll) 1e17;
const int inf = (ll) 2e9 + 7, mod = (ll) 998244353;

const int mxn = 2e5 + 5, mxm = MASK(5) + 1, LOG = 18;

void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }


//#include "crocodile.h"

struct Edge {
    int v, w;
    Edge(int _v, int _w) : v(_v), w(_w) {};
};
int n, m;
vector<Edge> g[mxn];

pair<int, int> a[4];
bool update(pair<int, int> &best, pair<int, int> &secondBest, pair<int, int> cur) {

    a[0] = cur;
    a[1] = best;
    a[2] = secondBest;
    sort(a, a + 3);

    best = a[0];
    int dist = secondBest.first;
    secondBest = a[1].second == best.second ? a[2] : a[1];

    return dist > secondBest.first;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {

    n = N; m = M;
    forn(i, 0, m - 1) {
        int u = R[i][0];
        int v = R[i][1];
        g[u].pb(Edge(v, L[i]));
        g[v].pb(Edge(u, L[i]));
    }
    vector<pair<int, int>> best(n, mp(inf, inf)), secondBest;
    secondBest = best;
    forn(i, 0, K - 1) {
        int node = P[i];
        best[node] = secondBest[node] = mp(0, 0);
    }
    priority_queue<pair<int, int>> pq;
    forn(i, 0, n - 1) if (secondBest[i].first != inf) {
        pq.push(mp(0, i));
    }

    while (!pq.empty()) {
        pair<ll, int> top = pq.top(); pq.pop();
        int u = top.second; ll dist = -top.fi;

//        if (secondBest[u].first != dist)
//            continue;

        for (Edge i : g[u]) {
            int v = i.v;
            ll nxt = dist + i.w;

            if (update(best[v], secondBest[v], mp(nxt, u))) {
                pq.push(mp(-secondBest[v].first, v));
            }
        }
    }

    return secondBest[0].first;
}

//int main(void) {
//
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//
//    #define TASK "task"
//    if (fopen(TASK".inp", "r")) {
//        freopen(TASK".inp", "r", stdin);
//        freopen(TASK".out", "w", stdout);
//    }
//
//    int n = 5, m = 4, k = 3;
//    int r[][2] = {{0, 1}, {0, 2}, {3, 2}, {2, 4}};
//    int l[] = {2, 3, 1, 4};
//    int p[] = {1, 3, 4};
//
//    cout << travel_plan(n, m, r, l, k, p);
//
//    return 0;
//}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5020 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 2 ms 5040 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5020 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 2 ms 5040 KB Output is correct
9 Correct 4 ms 5224 KB Output is correct
10 Correct 3 ms 4968 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 6 ms 5480 KB Output is correct
13 Correct 4 ms 5576 KB Output is correct
14 Correct 3 ms 5012 KB Output is correct
15 Correct 4 ms 5224 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5020 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 2 ms 5040 KB Output is correct
9 Correct 4 ms 5224 KB Output is correct
10 Correct 3 ms 4968 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 6 ms 5480 KB Output is correct
13 Correct 4 ms 5576 KB Output is correct
14 Correct 3 ms 5012 KB Output is correct
15 Correct 4 ms 5224 KB Output is correct
16 Correct 350 ms 59888 KB Output is correct
17 Correct 46 ms 17232 KB Output is correct
18 Correct 62 ms 18456 KB Output is correct
19 Correct 363 ms 64460 KB Output is correct
20 Correct 190 ms 52048 KB Output is correct
21 Correct 30 ms 10296 KB Output is correct
22 Correct 276 ms 48728 KB Output is correct