oj.uz

Submission #1001970

# Submission time Handle Problem Language Result Execution time Memory
1001970 2024-06-19T08:52:38 Z underwaterkillerwhale Cyberland (APIO23_cyberland) C++17
97 / 100
 606 ms 62716 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, 62)) 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, 62)) {
                    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

# Verdict Execution time Memory Grader output
1 Correct 48 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 141 ms 4176 KB Correct.
2 Correct 155 ms 4436 KB Correct.
3 Correct 162 ms 4436 KB Correct.
4 Correct 148 ms 4296 KB Correct.
5 Correct 147 ms 4332 KB Correct.
6 Correct 138 ms 9372 KB Correct.
7 Correct 203 ms 9548 KB Correct.
8 Correct 110 ms 14592 KB Correct.
9 Correct 123 ms 3676 KB Correct.
10 Correct 116 ms 3664 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 5156 KB Correct.
2 Correct 207 ms 5064 KB Correct.
3 Correct 193 ms 5048 KB Correct.
4 Correct 150 ms 3664 KB Correct.
5 Correct 152 ms 3876 KB Correct.
6 Correct 51 ms 10704 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 43984 KB Correct.
2 Correct 128 ms 5040 KB Correct.
3 Correct 111 ms 4776 KB Correct.
4 Correct 145 ms 4972 KB Correct.
5 Correct 91 ms 3868 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 4372 KB Correct.
2 Correct 86 ms 4540 KB Correct.
3 Correct 97 ms 4436 KB Correct.
4 Correct 102 ms 9736 KB Correct.
5 Correct 69 ms 3664 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 5064 KB Correct.
2 Correct 101 ms 4988 KB Correct.
3 Correct 40 ms 48464 KB Correct.
4 Correct 87 ms 12608 KB Correct.
5 Correct 88 ms 3888 KB Correct.
6 Correct 107 ms 5100 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 5088 KB Correct.
2 Correct 21 ms 4696 KB Correct.
3 Correct 55 ms 60720 KB Correct.
4 Correct 44 ms 17980 KB Correct.
5 Correct 606 ms 51904 KB Correct.
6 Correct 286 ms 25796 KB Correct.
7 Correct 43 ms 18700 KB Correct.
8 Correct 48 ms 6712 KB Correct.
9 Correct 115 ms 5012 KB Correct.
10 Correct 113 ms 4940 KB Correct.
11 Correct 57 ms 5436 KB Correct.
12 Correct 144 ms 5032 KB Correct.
13 Correct 122 ms 4980 KB Correct.
14 Correct 47 ms 31736 KB Correct.
15 Correct 42 ms 12004 KB Correct.
16 Correct 123 ms 4936 KB Correct.
17 Correct 141 ms 5052 KB Correct.
18 Correct 137 ms 5156 KB Correct.
19 Correct 348 ms 5880 KB Correct.
20 Correct 11 ms 2908 KB Correct.
21 Correct 10 ms 3768 KB Correct.
22 Correct 19 ms 5444 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 5668 KB Correct.
2 Correct 42 ms 5588 KB Correct.
3 Incorrect 263 ms 62716 KB Wrong Answer.
4 Halted 0 ms 0 KB -