oj.uz

답안 #1002101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1002101 2024-06-19T09:55:58 Z underwaterkillerwhale 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 461 ms 66900 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 = 1e18;
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][70];
    bool canGo[N];
    double PW[70];

    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, K) dp[i][k] = INF;
        PW[0] = 1;
        rep (i, 1, K) PW[i] = PW[i - 1] / 2;
        BFS();
        reb (k, K, 0) {
            priority_queue<pair<double,int>, vector<pair<double,int>>, greater<pair<double,int>> > pq;
            rep (i, 1, n) {
                if (i == 1 || (a[i] == 0 && canGo[i] == 1)) {
                    dp[i][k] = 0;
                }
                if (dp[i][k] != INF) pq.push({dp[i][k], i});
            }
            while (!pq.empty()) {
                int u = pq.top().se;
                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 * PW[k]) {
                            dp[v][k] = dp[u][k] + 1.0 * w * PW[k];
                            if (v != H) pq.push({dp[v][k], v});
                        }
                    }
                    else if (a[v] == 2) {
                        if (dp[v][k] > dp[u][k] + 1.0 * w * PW[k]) {
                            dp[v][k] = dp[u][k] + 1.0 * w * PW[k];
                            if (v != H) pq.push({dp[v][k], v});
                        }
                        if (k >= 1 && dp[v][k - 1] > dp[u][k] + 1.0 * w * PW[k]) {
                            dp[v][k - 1] = dp[u][k] + 1.0 * w * PW[k];
                        }
                    }
                }
            }
        }
        if (dp[H][0] != INF) return dp[H][0];
        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;
    K = min(K, 65);
    ++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

*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 3160 KB Correct.
2 Correct 22 ms 3208 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 4184 KB Correct.
2 Correct 68 ms 4432 KB Correct.
3 Correct 64 ms 4688 KB Correct.
4 Correct 67 ms 4436 KB Correct.
5 Correct 68 ms 4436 KB Correct.
6 Correct 168 ms 9792 KB Correct.
7 Correct 195 ms 9808 KB Correct.
8 Correct 95 ms 15452 KB Correct.
9 Correct 50 ms 3800 KB Correct.
10 Correct 58 ms 3664 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 4432 KB Correct.
2 Correct 78 ms 4432 KB Correct.
3 Correct 75 ms 4436 KB Correct.
4 Correct 59 ms 3676 KB Correct.
5 Correct 58 ms 3664 KB Correct.
6 Correct 42 ms 8200 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 40428 KB Correct.
2 Correct 73 ms 4436 KB Correct.
3 Correct 59 ms 4368 KB Correct.
4 Correct 65 ms 4436 KB Correct.
5 Correct 43 ms 3676 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 4432 KB Correct.
2 Correct 45 ms 4444 KB Correct.
3 Correct 46 ms 4432 KB Correct.
4 Correct 106 ms 9808 KB Correct.
5 Correct 34 ms 3668 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 4444 KB Correct.
2 Correct 41 ms 4432 KB Correct.
3 Correct 60 ms 51540 KB Correct.
4 Correct 73 ms 7812 KB Correct.
5 Correct 70 ms 3792 KB Correct.
6 Correct 48 ms 4440 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 4436 KB Correct.
2 Correct 14 ms 3932 KB Correct.
3 Correct 461 ms 64372 KB Correct.
4 Correct 248 ms 18492 KB Correct.
5 Correct 405 ms 29720 KB Correct.
6 Correct 184 ms 14396 KB Correct.
7 Correct 236 ms 19596 KB Correct.
8 Correct 146 ms 6964 KB Correct.
9 Correct 54 ms 4276 KB Correct.
10 Correct 68 ms 4264 KB Correct.
11 Correct 139 ms 5460 KB Correct.
12 Correct 70 ms 4436 KB Correct.
13 Correct 64 ms 4480 KB Correct.
14 Correct 226 ms 33228 KB Correct.
15 Correct 181 ms 12556 KB Correct.
16 Correct 63 ms 4688 KB Correct.
17 Correct 73 ms 4588 KB Correct.
18 Correct 67 ms 4412 KB Correct.
19 Correct 194 ms 5504 KB Correct.
20 Correct 6 ms 2908 KB Correct.
21 Correct 6 ms 3448 KB Correct.
22 Correct 13 ms 3904 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 4484 KB Correct.
2 Correct 23 ms 4060 KB Correct.
3 Incorrect 197 ms 66900 KB Wrong Answer.
4 Halted 0 ms 0 KB -