oj.uz

Submission #750259

# Submission time Handle Problem Language Result Execution time Memory
750259 2023-05-29T08:42:41 Z singlabharat Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 157968 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, 69);

    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 468 KB Correct.
2 Correct 23 ms 492 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 788 KB Correct.
2 Correct 31 ms 724 KB Correct.
3 Correct 30 ms 696 KB Correct.
4 Correct 32 ms 696 KB Correct.
5 Correct 30 ms 696 KB Correct.
6 Correct 28 ms 3884 KB Correct.
7 Correct 34 ms 3820 KB Correct.
8 Correct 18 ms 7508 KB Correct.
9 Correct 29 ms 416 KB Correct.
10 Correct 27 ms 424 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 720 KB Correct.
2 Correct 30 ms 756 KB Correct.
3 Correct 28 ms 752 KB Correct.
4 Correct 34 ms 412 KB Correct.
5 Correct 30 ms 436 KB Correct.
6 Correct 7 ms 3412 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 23396 KB Correct.
2 Correct 339 ms 1028 KB Correct.
3 Correct 291 ms 1112 KB Correct.
4 Correct 296 ms 892 KB Correct.
5 Correct 261 ms 428 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 724 KB Correct.
2 Correct 27 ms 624 KB Correct.
3 Correct 28 ms 660 KB Correct.
4 Correct 25 ms 3668 KB Correct.
5 Correct 23 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 732 KB Correct.
2 Correct 23 ms 644 KB Correct.
3 Correct 40 ms 7160 KB Correct.
4 Correct 16 ms 2584 KB Correct.
5 Correct 25 ms 388 KB Correct.
6 Correct 25 ms 668 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 1496 KB Correct.
2 Correct 44 ms 1596 KB Correct.
3 Correct 709 ms 28244 KB Correct.
4 Correct 591 ms 7696 KB Correct.
5 Correct 1101 ms 48408 KB Correct.
6 Correct 507 ms 23860 KB Correct.
7 Correct 566 ms 7548 KB Correct.
8 Correct 619 ms 1740 KB Correct.
9 Correct 257 ms 1528 KB Correct.
10 Correct 247 ms 1444 KB Correct.
11 Correct 625 ms 952 KB Correct.
12 Correct 281 ms 1416 KB Correct.
13 Correct 313 ms 1496 KB Correct.
14 Correct 470 ms 9500 KB Correct.
15 Correct 582 ms 3484 KB Correct.
16 Correct 267 ms 1524 KB Correct.
17 Correct 323 ms 1428 KB Correct.
18 Correct 288 ms 1508 KB Correct.
19 Correct 684 ms 1636 KB Correct.
20 Correct 23 ms 552 KB Correct.
21 Correct 18 ms 852 KB Correct.
22 Correct 37 ms 3144 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 994 ms 4384 KB Correct.
2 Correct 127 ms 4276 KB Correct.
3 Correct 660 ms 67660 KB Correct.
4 Correct 1147 ms 4688 KB Correct.
5 Execution timed out 3077 ms 157968 KB Time limit exceeded
6 Halted 0 ms 0 KB -