oj.uz

Submission #752036

# Submission time Handle Problem Language Result Execution time Memory
752036 2023-06-02T06:55:56 Z singlabharat Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 289448 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, 70);

    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>;

    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;
    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});
            }
        }
    }

    double ans = *min_element(begin(dist[H]), end(dist[H]));
    return (ans == INF ? -1 : ans);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 468 KB Correct.
2 Correct 24 ms 464 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 676 KB Correct.
2 Correct 37 ms 696 KB Correct.
3 Correct 29 ms 724 KB Correct.
4 Correct 27 ms 660 KB Correct.
5 Correct 29 ms 668 KB Correct.
6 Correct 35 ms 3848 KB Correct.
7 Correct 46 ms 3788 KB Correct.
8 Correct 19 ms 7508 KB Correct.
9 Correct 36 ms 340 KB Correct.
10 Correct 28 ms 416 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 632 KB Correct.
2 Correct 33 ms 696 KB Correct.
3 Correct 30 ms 712 KB Correct.
4 Correct 34 ms 432 KB Correct.
5 Correct 33 ms 416 KB Correct.
6 Correct 8 ms 3284 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 21304 KB Correct.
2 Correct 584 ms 788 KB Correct.
3 Correct 463 ms 752 KB Correct.
4 Correct 525 ms 704 KB Correct.
5 Correct 377 ms 484 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 656 KB Correct.
2 Correct 29 ms 636 KB Correct.
3 Correct 28 ms 672 KB Correct.
4 Correct 29 ms 3708 KB Correct.
5 Correct 30 ms 400 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 596 KB Correct.
2 Correct 26 ms 676 KB Correct.
3 Correct 51 ms 27896 KB Correct.
4 Correct 24 ms 2556 KB Correct.
5 Correct 35 ms 416 KB Correct.
6 Correct 29 ms 812 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 2168 KB Correct.
2 Correct 91 ms 3608 KB Correct.
3 Correct 1531 ms 27204 KB Correct.
4 Correct 1171 ms 7056 KB Correct.
5 Correct 2451 ms 81280 KB Correct.
6 Correct 1282 ms 40172 KB Correct.
7 Correct 1209 ms 6960 KB Correct.
8 Correct 1067 ms 1524 KB Correct.
9 Correct 496 ms 2292 KB Correct.
10 Correct 486 ms 2336 KB Correct.
11 Correct 1060 ms 964 KB Correct.
12 Correct 502 ms 1964 KB Correct.
13 Correct 524 ms 2364 KB Correct.
14 Correct 1053 ms 9184 KB Correct.
15 Correct 1258 ms 2840 KB Correct.
16 Correct 512 ms 2064 KB Correct.
17 Correct 636 ms 2060 KB Correct.
18 Correct 585 ms 1584 KB Correct.
19 Correct 1560 ms 2156 KB Correct.
20 Correct 32 ms 592 KB Correct.
21 Correct 36 ms 1216 KB Correct.
22 Correct 105 ms 5240 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1911 ms 7668 KB Correct.
2 Correct 307 ms 14080 KB Correct.
3 Correct 673 ms 67656 KB Correct.
4 Correct 2857 ms 4700 KB Correct.
5 Execution timed out 3066 ms 289448 KB Time limit exceeded
6 Halted 0 ms 0 KB -