oj.uz

Submission #1094222

# Submission time Handle Problem Language Result Execution time Memory
1094222 2024-09-29T03:24:52 Z anhthi Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 307 ms 64456 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; }

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

bool vis[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));
    }
    memset(vis, 0, sizeof vis);

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

        if (vis[u]) continue;
        vis[u] = true;

        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 = 6, m = 6, k = 3;
//    int r[][2] = {{0, 1}, {0, 2}, {2, 5}, {2, 4}, {1, 4}, {1, 3}};
//    int l[] = {3, 3, 3, 5, 5, 3};
//    int p[] = {3, 4, 5};
//
//    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 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 5364 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 5364 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 5 ms 5468 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 3 ms 5468 KB Output is correct
12 Correct 4 ms 5668 KB Output is correct
13 Correct 5 ms 5676 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 3 ms 5212 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 5364 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 5 ms 5468 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 3 ms 5468 KB Output is correct
12 Correct 4 ms 5668 KB Output is correct
13 Correct 5 ms 5676 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 3 ms 5212 KB Output is correct
16 Correct 265 ms 60068 KB Output is correct
17 Correct 56 ms 16976 KB Output is correct
18 Correct 58 ms 18512 KB Output is correct
19 Correct 307 ms 64456 KB Output is correct
20 Correct 199 ms 52052 KB Output is correct
21 Correct 24 ms 10580 KB Output is correct
22 Correct 210 ms 48796 KB Output is correct