oj.uz

답안 #750155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750155 2023-05-29T07:17:14 Z singlabharat 사이버랜드 (APIO23_cyberland) C++17
15 / 100
 784 ms 2097152 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) {
    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>;

    // {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;
    while (!empty(pq)) {
        auto [_, divs, u] = pq.top();
        pq.pop();
        for (auto [v, w] : g[u]) {
            if (arr[u] == 0) {
                if (w < dist[v][divs]) {
                    dist[v][divs] = w;
                    pq.push({dist[v][divs], divs, v});
                }
            } else if (arr[u] == 1) {
                if (dist[u][divs] + w < dist[v][divs]) {
                    dist[v][divs] = dist[u][divs] + w;
                    pq.push({dist[v][divs], divs, v});
                }

            } else {
                if (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 = INF;
    fo(divs, K + 1) domin(ans, dist[H][divs]);
    return (ans == INF ? -1 : ans);
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 704 KB Correct.
2 Correct 32 ms 664 KB Correct.
3 Correct 29 ms 676 KB Correct.
4 Correct 30 ms 696 KB Correct.
5 Correct 29 ms 684 KB Correct.
6 Correct 25 ms 3864 KB Correct.
7 Correct 45 ms 3796 KB Correct.
8 Correct 18 ms 7472 KB Correct.
9 Correct 30 ms 420 KB Correct.
10 Correct 27 ms 416 KB Correct.

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 696 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 21264 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 676 KB Correct.
2 Correct 32 ms 664 KB Correct.
3 Correct 31 ms 672 KB Correct.
4 Correct 32 ms 3708 KB Correct.
5 Correct 28 ms 412 KB Correct.

Subtask #6
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 712 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 434 ms 1976 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 784 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -