oj.uz

Submission #1002078

# Submission time Handle Problem Language Result Execution time Memory
1002078 2024-06-19T09:44:19 Z underwaterkillerwhale Cyberland (APIO23_cyberland) C++17
97 / 100
 634 ms 66796 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;
        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] +  w * PW[k]) {
                        dp[v][k] = dp[u][k] + 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] + 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]});
                    }
                    if (k >= 1 && dp[v][k - 1] > dp[u][k] + 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 26 ms 3160 KB Correct.
2 Correct 27 ms 3164 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 4176 KB Correct.
2 Correct 142 ms 4580 KB Correct.
3 Correct 132 ms 4436 KB Correct.
4 Correct 140 ms 4436 KB Correct.
5 Correct 142 ms 4344 KB Correct.
6 Correct 130 ms 9808 KB Correct.
7 Correct 167 ms 10040 KB Correct.
8 Correct 84 ms 15580 KB Correct.
9 Correct 115 ms 3664 KB Correct.
10 Correct 112 ms 3668 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 5212 KB Correct.
2 Correct 204 ms 5076 KB Correct.
3 Correct 210 ms 5124 KB Correct.
4 Correct 148 ms 3692 KB Correct.
5 Correct 150 ms 3824 KB Correct.
6 Correct 49 ms 10956 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 46200 KB Correct.
2 Correct 122 ms 4920 KB Correct.
3 Correct 109 ms 5036 KB Correct.
4 Correct 134 ms 4968 KB Correct.
5 Correct 87 ms 3904 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 4448 KB Correct.
2 Correct 85 ms 4436 KB Correct.
3 Correct 103 ms 4432 KB Correct.
4 Correct 99 ms 10012 KB Correct.
5 Correct 64 ms 3664 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 4968 KB Correct.
2 Correct 91 ms 5000 KB Correct.
3 Correct 41 ms 51592 KB Correct.
4 Correct 82 ms 12864 KB Correct.
5 Correct 101 ms 3664 KB Correct.
6 Correct 107 ms 5040 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 4952 KB Correct.
2 Correct 21 ms 4920 KB Correct.
3 Correct 56 ms 64512 KB Correct.
4 Correct 51 ms 19344 KB Correct.
5 Correct 634 ms 53384 KB Correct.
6 Correct 300 ms 26308 KB Correct.
7 Correct 54 ms 19888 KB Correct.
8 Correct 42 ms 6960 KB Correct.
9 Correct 113 ms 5020 KB Correct.
10 Correct 111 ms 4932 KB Correct.
11 Correct 55 ms 5696 KB Correct.
12 Correct 124 ms 5112 KB Correct.
13 Correct 122 ms 5212 KB Correct.
14 Correct 51 ms 33976 KB Correct.
15 Correct 42 ms 12672 KB Correct.
16 Correct 115 ms 5160 KB Correct.
17 Correct 139 ms 5048 KB Correct.
18 Correct 137 ms 5052 KB Correct.
19 Correct 313 ms 6144 KB Correct.
20 Correct 9 ms 2908 KB Correct.
21 Correct 9 ms 3768 KB Correct.
22 Correct 18 ms 5488 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 5752 KB Correct.
2 Correct 45 ms 6152 KB Correct.
3 Incorrect 193 ms 66796 KB Wrong Answer.
4 Halted 0 ms 0 KB -