oj.uz

Submission #1001995

# Submission time Handle Problem Language Result Execution time Memory
1001995 2024-06-19T09:02:18 Z underwaterkillerwhale Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 397352 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][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;
        BFS();
        priority_queue<Data, vector<Data>, cmp> pq;
        rep (i, 1, n) {
            if (i == 1 || (a[i] == 0 && canGo[i] == 1)) {
                rep (k, 0, K) {
                    dp[i][k] = 0;
                    pq.push({i, k, 0});
                }
            }
        }
        PW[0] = 1;
        rep (i, 1, K) PW[i] = PW[i - 1] / 2;
        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 * PW[k]) {
                        dp[v][k] = dp[u][k] + 1.0 * w * PW[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 * PW[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 * PW[k]) {
                        dp[v][k - 1] = dp[u][k] + 1.0 * w * PW[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;
    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

*/

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3176 KB Correct.
2 Correct 28 ms 3164 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 4216 KB Correct.
2 Correct 145 ms 4572 KB Correct.
3 Correct 136 ms 4332 KB Correct.
4 Correct 141 ms 4456 KB Correct.
5 Correct 149 ms 4364 KB Correct.
6 Correct 148 ms 9680 KB Correct.
7 Correct 202 ms 10048 KB Correct.
8 Correct 96 ms 15444 KB Correct.
9 Correct 120 ms 3788 KB Correct.
10 Correct 121 ms 3808 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 5152 KB Correct.
2 Correct 216 ms 5140 KB Correct.
3 Correct 201 ms 5096 KB Correct.
4 Correct 157 ms 3740 KB Correct.
5 Correct 155 ms 3736 KB Correct.
6 Correct 61 ms 10956 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 46308 KB Correct.
2 Correct 129 ms 5028 KB Correct.
3 Correct 115 ms 5068 KB Correct.
4 Correct 120 ms 5008 KB Correct.
5 Correct 92 ms 3668 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 4408 KB Correct.
2 Correct 84 ms 4580 KB Correct.
3 Correct 98 ms 4436 KB Correct.
4 Correct 109 ms 9884 KB Correct.
5 Correct 65 ms 3528 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 5060 KB Correct.
2 Correct 94 ms 5028 KB Correct.
3 Correct 44 ms 51536 KB Correct.
4 Correct 87 ms 12876 KB Correct.
5 Correct 87 ms 3664 KB Correct.
6 Correct 106 ms 4996 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 5004 KB Correct.
2 Correct 26 ms 4952 KB Correct.
3 Correct 60 ms 64552 KB Correct.
4 Correct 43 ms 19008 KB Correct.
5 Correct 664 ms 53440 KB Correct.
6 Correct 305 ms 26396 KB Correct.
7 Correct 48 ms 19732 KB Correct.
8 Correct 44 ms 6968 KB Correct.
9 Correct 114 ms 5108 KB Correct.
10 Correct 108 ms 4908 KB Correct.
11 Correct 53 ms 5620 KB Correct.
12 Correct 124 ms 5152 KB Correct.
13 Correct 122 ms 5184 KB Correct.
14 Correct 47 ms 33760 KB Correct.
15 Correct 42 ms 12772 KB Correct.
16 Correct 121 ms 5052 KB Correct.
17 Correct 139 ms 5192 KB Correct.
18 Correct 157 ms 5088 KB Correct.
19 Correct 349 ms 6136 KB Correct.
20 Correct 10 ms 2908 KB Correct.
21 Correct 10 ms 3672 KB Correct.
22 Correct 19 ms 5588 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3079 ms 397352 KB Time limit exceeded
2 Halted 0 ms 0 KB -