oj.uz

답안 #752035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752035 2023-06-02T06:53:00 Z singlabharat 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 289504 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>;

    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;

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

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 468 KB Correct.
2 Correct 22 ms 468 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 688 KB Correct.
2 Correct 32 ms 700 KB Correct.
3 Correct 30 ms 684 KB Correct.
4 Correct 31 ms 696 KB Correct.
5 Correct 31 ms 680 KB Correct.
6 Correct 27 ms 3936 KB Correct.
7 Correct 38 ms 3800 KB Correct.
8 Correct 17 ms 7508 KB Correct.
9 Correct 31 ms 428 KB Correct.
10 Correct 30 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 596 KB Correct.
2 Correct 35 ms 688 KB Correct.
3 Correct 33 ms 668 KB Correct.
4 Correct 33 ms 340 KB Correct.
5 Correct 36 ms 464 KB Correct.
6 Correct 7 ms 3284 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 322 ms 21312 KB Correct.
2 Correct 553 ms 732 KB Correct.
3 Correct 474 ms 788 KB Correct.
4 Correct 532 ms 792 KB Correct.
5 Correct 381 ms 448 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 684 KB Correct.
2 Correct 28 ms 628 KB Correct.
3 Correct 27 ms 656 KB Correct.
4 Correct 28 ms 3704 KB Correct.
5 Correct 24 ms 420 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 632 KB Correct.
2 Correct 24 ms 636 KB Correct.
3 Correct 46 ms 7172 KB Correct.
4 Correct 20 ms 2568 KB Correct.
5 Correct 28 ms 424 KB Correct.
6 Correct 30 ms 680 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 502 ms 2352 KB Correct.
2 Correct 90 ms 3620 KB Correct.
3 Correct 1492 ms 27292 KB Correct.
4 Correct 1191 ms 6912 KB Correct.
5 Correct 2357 ms 81268 KB Correct.
6 Correct 1202 ms 40220 KB Correct.
7 Correct 1156 ms 7004 KB Correct.
8 Correct 1069 ms 1544 KB Correct.
9 Correct 428 ms 1968 KB Correct.
10 Correct 402 ms 2252 KB Correct.
11 Correct 1037 ms 1004 KB Correct.
12 Correct 468 ms 2032 KB Correct.
13 Correct 495 ms 2136 KB Correct.
14 Correct 1018 ms 8968 KB Correct.
15 Correct 1284 ms 2764 KB Correct.
16 Correct 442 ms 2084 KB Correct.
17 Correct 556 ms 2144 KB Correct.
18 Correct 476 ms 1664 KB Correct.
19 Correct 1202 ms 2388 KB Correct.
20 Correct 26 ms 512 KB Correct.
21 Correct 32 ms 1144 KB Correct.
22 Correct 107 ms 5144 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1639 ms 7692 KB Correct.
2 Correct 302 ms 14136 KB Correct.
3 Correct 704 ms 67668 KB Correct.
4 Correct 2751 ms 4700 KB Correct.
5 Execution timed out 3039 ms 289504 KB Time limit exceeded
6 Halted 0 ms 0 KB -