oj.uz

답안 #1001972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1001972 2024-06-19T08:53:14 Z underwaterkillerwhale 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 397272 KB 
#ifdef ONLINE_JUDGE
    #include "cyberland.h"
#endif

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N  = 1e5 + 7;
const int Mod = 1e9 +7;
const int szBL = 50;
const ll INF = 1e15;
const int BASE = 137;

struct toEdge {
    int v, w;
};

int n, m, K, H;
int a[N];
vector<toEdge> ke[N];

namespace sub1 {
    double dist[N];

    double solution() {
        rep (i, 1, n) dist[i] = INF;
        priority_queue<pair<double, int>, vector<pair<double,int>>, greater<pair<double, int>> > Q; Q.push({0, 1});
        dist[1] = 0;
        while (!Q.empty()) {
            int u = Q.top().se;
            Q.pop();
            iter (&id, ke[u]) {
                int v = id.v, w = id.w;
                double delta = dist[u] + w;
                if (a[v] == 2) delta /= 2.0;
                else if (a[v] == 0) delta = 0;
                if (dist[v] > delta) {
                    dist[v] = delta;
                    if (v != H) {
                        Q.push({dist[v], v});
                    }
                }
            }
        }
        if (dist[H] == INF) return -1;
        else return dist[H];
    }
}

namespace sub160907 {
    struct Data {
            ll u, k;
            double val;
    };
    struct cmp {
        bool operator () (Data A, Data B) { return A.val > B.val; }
    };
    double dp[N][65];
    bool canGo[N];

    void BFS () {
        rep (i, 1, n) canGo[i] = 0;
        queue<int> Q;
        Q.push(1);
        canGo[1] = 1;
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            iter (&id, ke[u]) {
                if (!canGo[id.v]) {
                    canGo[id.v] = 1;
                    if (id.v != H) Q.push(id.v);
                }
            }
        }
    }

    double solution() {
        rep (i, 1, n) rep (k, 0, min(K, 63)) dp[i][k] = INF;
        BFS();
        priority_queue<Data, vector<Data>, cmp> pq;
        rep (i, 1, n) {
            if (i == 1 || (a[i] == 0 && canGo[i] == 1)) {
                rep (k, 0, min(K, 63)) {
                    dp[i][k] = 0;
                    pq.push({i, k, 0});
                }
            }
        }
        ll res = INF;
        while (!pq.empty()) {
            int u = pq.top().u, k = pq.top().k;
            if (u == H && k == 0) {
                return dp[u][k];
            }
            pq.pop();
            iter (&id, ke[u]) {
                ll v = id.v, w = id.w;
                if (a[v] == 0) continue;
                if (a[v] == 1) {
                    if (dp[v][k] > dp[u][k] + 1.0 * w / (1LL << k)) {
                        dp[v][k] = dp[u][k] + 1.0 * w / (1LL << k);
                        if (v != H || k == 0) pq.push({v, k, dp[v][k]});
                    }
                }
                else if (a[v] == 2) {
                    if (dp[v][k] > dp[u][k] + 1.0 * w / (1LL << k)) {
                        dp[v][k] = dp[u][k] + 1.0 * w / (1LL << k);
                        if (v != H || k == 0) pq.push({v, k, dp[v][k]});
                    }
                    if (k >= 1 && dp[v][k - 1] > dp[u][k] + 1.0 * w / (1LL << k)) {
                        dp[v][k - 1] = dp[u][k] + 1.0 * w / (1LL << k);
                        if (v != H || k == 0) pq.push({v, k - 1, dp[v][k - 1]});
                    }
                }
            }
        }
        return -1;
    }
}

double solve (int _n, int _m, int _K, int _H, vector<int> _U, vector<int> _V, vector<int> _W, vector<int> _A) {
    n = _n;
    m = _m;
    K = _K;
    H = _H;
    ++H;
    rep (i ,1, n) ke[i].clear();
    rep (i, 1, n) {
        a[i] = _A[i - 1];
    }
    rep (i, 0, m - 1) {
        int u = _U[i], v = _V[i], w = _W[i];
        ++u, ++v;
        ke[u].push_back({v, w});
        ke[v].push_back({u, w});
    }
//    if (n <= 3 && K <= 30)
//        return sub1 :: solution();
//    else
        return sub160907 :: solution();
}

//void solution() {
//    cin >> n >> m >> K >> H;
//    ++H;
//    rep (i, 1, n) cin >> a[i];
//    rep (i, 1, m) {
//        int u, v, w;
//        cin >> u >> v>> w;
//        ++u, ++v;
//        ke[u].push_back({v, w});
//        ke[v].push_back({u, w});
//    }
//    cout << sub1 :: solution () <<"\n";
//    cout << sub160907 :: solution () <<"\n";
//}
//#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
//int main () {
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
////    file ("c");
//    int num_Test = 1;
//    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}

/*
1
3 2 30
2
1 2 1
1 2 12
2 0 4

1
4 4 30
3
1 1 2 1
0 1 5
0 2 5
1 3 2
2 3 4


3 2
0 1 5
0 2 5
1
1 2

*/

Compilation message

cyberland.cpp: In function 'double sub160907::solution()':
cyberland.cpp:107:12: warning: unused variable 'res' [-Wunused-variable]
  107 |         ll res = INF;
      |            ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 2904 KB Correct.
2 Correct 27 ms 2904 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 3416 KB Correct.
2 Correct 136 ms 3432 KB Correct.
3 Correct 134 ms 3436 KB Correct.
4 Correct 132 ms 3416 KB Correct.
5 Correct 134 ms 3416 KB Correct.
6 Correct 123 ms 8612 KB Correct.
7 Correct 171 ms 8568 KB Correct.
8 Correct 79 ms 14172 KB Correct.
9 Correct 120 ms 2908 KB Correct.
10 Correct 118 ms 2904 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 4064 KB Correct.
2 Correct 200 ms 4164 KB Correct.
3 Correct 177 ms 4200 KB Correct.
4 Correct 155 ms 2904 KB Correct.
5 Correct 150 ms 2996 KB Correct.
6 Correct 48 ms 10704 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 42436 KB Correct.
2 Correct 119 ms 4056 KB Correct.
3 Correct 110 ms 3892 KB Correct.
4 Correct 107 ms 4024 KB Correct.
5 Correct 85 ms 2976 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 3416 KB Correct.
2 Correct 78 ms 3416 KB Correct.
3 Correct 93 ms 3472 KB Correct.
4 Correct 111 ms 8720 KB Correct.
5 Correct 68 ms 2904 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 4320 KB Correct.
2 Correct 92 ms 4108 KB Correct.
3 Correct 40 ms 46672 KB Correct.
4 Correct 90 ms 11844 KB Correct.
5 Correct 87 ms 2988 KB Correct.
6 Correct 110 ms 4124 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 4048 KB Correct.
2 Correct 21 ms 4696 KB Correct.
3 Correct 52 ms 58456 KB Correct.
4 Correct 41 ms 15888 KB Correct.
5 Correct 636 ms 50344 KB Correct.
6 Correct 288 ms 24268 KB Correct.
7 Correct 39 ms 17132 KB Correct.
8 Correct 43 ms 4868 KB Correct.
9 Correct 114 ms 4140 KB Correct.
10 Correct 113 ms 4100 KB Correct.
11 Correct 53 ms 3652 KB Correct.
12 Correct 123 ms 4044 KB Correct.
13 Correct 120 ms 4128 KB Correct.
14 Correct 43 ms 29872 KB Correct.
15 Correct 40 ms 10164 KB Correct.
16 Correct 121 ms 4132 KB Correct.
17 Correct 139 ms 4108 KB Correct.
18 Correct 131 ms 4056 KB Correct.
19 Correct 343 ms 4092 KB Correct.
20 Correct 13 ms 2908 KB Correct.
21 Correct 10 ms 3600 KB Correct.
22 Correct 19 ms 5332 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3105 ms 397272 KB Time limit exceeded
2 Halted 0 ms 0 KB -