oj.uz

Submission #750255

# Submission time Handle Problem Language Result Execution time Memory
750255 2023-05-29T08:39:35 Z singlabharat Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 160740 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
using si = set<int>;
using mii = map<int, int>;
#define sz(x) (int)size(x)
#define pb emplace_back
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define fr first
#define sc second
#define fo(i, end) for (int i = 0; i < end; i++)
#define foo(i, start, end) for (int i = start; i < end; i++)
template<typename T> inline void domin(T &x, T y) {if (y < x) x = y;}
template<typename T> inline void domax(T &x, T y) {if (y > x) x = y;}
template<typename T, typename U> ostream& operator<<(ostream &os, const pair<T, U> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template < typename T_container, typename T = typename enable_if < !is_same<T_container, string>::value, typename T_container::value_type >::type > ostream & operator<<(ostream &os, const T_container &a) { os << '{'; string sep; for (const T &x : a) os << sep << x, sep = ", "; return os << '}';}
void debug() {cerr << endl;}
template <typename Head, typename... Tail> void debug(Head h, Tail... t) {cerr << h << ' '; debug(t...);}
#ifdef singlabharat
#define debug(...) cerr << "(" << #__VA_ARGS__ << ") : ", debug(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MX = 2e5 + 2, MOD = 1e9 + 7;
double INF = 1e18;

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    domin(K, 80);

    vector<vpii> g(N);
    fo(i, M) {
        g[x[i]].pb(pair(y[i], c[i]));
        g[y[i]].pb(pair(x[i], c[i]));
    }

    using state = tuple<double, int, int>;

    vb vis(N);
    queue<int> q;
    q.push(0);
    vis[0] = true;
    while (!empty(q)) {
        int u = q.front();
        q.pop();
        if (u == H) continue;
        for (auto [v, _] : g[u]) {
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }

    if (!vis[H]) return -1;

    // {dist, divs, u}
    priority_queue < state, vector<state>, greater<state>> pq;
    vector<vector<double>> dist(N, vector<double>(K + 1, INF)); // min dist till u with k divs done
    pq.push({0.0, 0, 0});
    dist[0][0] = 0.0;
    fo(u, N) {
        if (arr[u] == 0 and vis[u]) {
            pq.push({0.0, 0, u});
            dist[u][0] = 0.0;
        }
    }

    while (!empty(pq)) {
        auto [_, divs, u] = pq.top();
        pq.pop();
        if (u == H) continue;
        for (auto [v, w] : g[u]) {
            if (arr[u] == 0 and w < dist[v][divs]) {
                dist[v][divs] = w;
                pq.push({dist[v][divs], divs, v});
            } if ((arr[u] == 1 or arr[u] == 2) and dist[u][divs] + w < dist[v][divs]) {
                dist[v][divs] = dist[u][divs] + w;
                pq.push({dist[v][divs], divs, v});

            } if (arr[u] == 2 and divs < K and dist[u][divs] / 2 + w < dist[v][divs + 1]) {
                dist[v][divs + 1] = dist[u][divs] / 2 + w;
                pq.push({dist[v][divs + 1], divs + 1, v});
            }
        }
    }

    return *min_element(begin(dist[H]), end(dist[H]));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 464 KB Correct.
2 Correct 23 ms 432 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 724 KB Correct.
2 Correct 29 ms 724 KB Correct.
3 Correct 28 ms 680 KB Correct.
4 Correct 29 ms 596 KB Correct.
5 Correct 31 ms 684 KB Correct.
6 Correct 28 ms 3936 KB Correct.
7 Correct 33 ms 3832 KB Correct.
8 Correct 17 ms 7524 KB Correct.
9 Correct 29 ms 424 KB Correct.
10 Correct 27 ms 412 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 832 KB Correct.
2 Correct 32 ms 692 KB Correct.
3 Correct 27 ms 736 KB Correct.
4 Correct 31 ms 340 KB Correct.
5 Correct 32 ms 340 KB Correct.
6 Correct 7 ms 3432 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 23352 KB Correct.
2 Correct 338 ms 1040 KB Correct.
3 Correct 286 ms 1208 KB Correct.
4 Correct 335 ms 900 KB Correct.
5 Correct 357 ms 424 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 684 KB Correct.
2 Correct 30 ms 620 KB Correct.
3 Correct 27 ms 652 KB Correct.
4 Correct 32 ms 3668 KB Correct.
5 Correct 24 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 708 KB Correct.
2 Correct 26 ms 600 KB Correct.
3 Correct 42 ms 7164 KB Correct.
4 Correct 19 ms 2584 KB Correct.
5 Correct 44 ms 416 KB Correct.
6 Correct 35 ms 668 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 1376 KB Correct.
2 Correct 49 ms 1528 KB Correct.
3 Correct 760 ms 28348 KB Correct.
4 Correct 754 ms 7600 KB Correct.
5 Correct 1326 ms 48396 KB Correct.
6 Correct 545 ms 23808 KB Correct.
7 Correct 580 ms 7544 KB Correct.
8 Correct 655 ms 1716 KB Correct.
9 Correct 265 ms 1456 KB Correct.
10 Correct 261 ms 1428 KB Correct.
11 Correct 649 ms 984 KB Correct.
12 Correct 275 ms 1472 KB Correct.
13 Correct 301 ms 1460 KB Correct.
14 Correct 457 ms 9520 KB Correct.
15 Correct 588 ms 3360 KB Correct.
16 Correct 262 ms 1444 KB Correct.
17 Correct 319 ms 1468 KB Correct.
18 Correct 289 ms 1428 KB Correct.
19 Correct 685 ms 1556 KB Correct.
20 Correct 24 ms 620 KB Correct.
21 Correct 18 ms 928 KB Correct.
22 Correct 38 ms 3144 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1141 ms 4624 KB Correct.
2 Correct 152 ms 4736 KB Correct.
3 Correct 772 ms 75484 KB Correct.
4 Correct 1225 ms 5200 KB Correct.
5 Execution timed out 3068 ms 160740 KB Time limit exceeded
6 Halted 0 ms 0 KB -