oj.uz

Submission #760438

# Submission time Handle Problem Language Result Execution time Memory
760438 2023-06-17T14:54:13 Z wiwiho Cyberland (APIO23_cyberland) C++17
100 / 100
 1675 ms 131064 KB 
#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb(a) emplace_back(a)
#define mp(a, b) make_pair(a, b)
#define ff first
#define ss second
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define SZ(a) int(a.size())
#ifdef LOCAL
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cerr << *l << " ", l++;
	cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif

typedef long long ll;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.ff << ',' << p.ss << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

double solve(int n, int m, int K, int H, vector<int> U, vector<int> V, vector<int> W, vector<int> arr){

    K = min(K, 70);   
    vector<ld> frac(K + 1); // 2^-i
    frac[0] = 1;
    for(int i = 1; i <= K; i++) frac[i] = frac[i - 1] / 2;

    vector<vector<pii>> g(n);
    for(int i = 0; i < m; i++){
        g[U[i]].pb(mp(V[i], W[i]));
        g[V[i]].pb(mp(U[i], W[i]));
    }

    vector<bool> ok(n);
    {
        queue<int> q;
        q.push(0);
        ok[0] = true;
        while(!q.empty()){
            int now = q.front();
            q.pop();
            for(auto [v, w] : g[now]){
                if(v == H) continue;
                if(ok[v]) continue;
                ok[v] = true;
                q.push(v);
            }
        }
    }

    vector<vector<ld>> dis(n, vector<ld>(K + 1, 1e100));
    priority_queue<pair<ld, pii>, vector<pair<ld, pii>>, greater<>> pq;
    vector<vector<bool>> vst(n, vector<bool>(K + 1));

    dis[H][0] = 0;
    pq.push(mp(0, mp(H, 0)));
    
    auto relax = [&](int now, int k, ld d){
        if(k > K) return;
        for(auto [v, w] : g[now]){
            if(v == H) continue;
            if(d + w * frac[k] >= dis[v][k]) continue;
            dis[v][k] = d + w * frac[k];
            pq.push(mp(dis[v][k], mp(v, k)));
        }
    };

    ld ans = 1e100;
    
    while(!pq.empty()){
        ld d = pq.top().ff;
        auto [now, k] = pq.top().ss;
        pq.pop();
        if(vst[now][k]) continue;
        if((ok[now] && arr[now] == 0) || now == 0) ans = min(ans, d);
        vst[now][k] = true;
        relax(now, k, d);
        if(arr[now] == 2) relax(now, k + 1, d);
    }

    if(ans > 1e20) return -1;
    else return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 388 KB Correct.
2 Correct 22 ms 600 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 980 KB Correct.
2 Correct 32 ms 980 KB Correct.
3 Correct 30 ms 1012 KB Correct.
4 Correct 31 ms 1028 KB Correct.
5 Correct 31 ms 1012 KB Correct.
6 Correct 29 ms 7064 KB Correct.
7 Correct 37 ms 7032 KB Correct.
8 Correct 20 ms 13908 KB Correct.
9 Correct 30 ms 452 KB Correct.
10 Correct 29 ms 452 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1012 KB Correct.
2 Correct 31 ms 920 KB Correct.
3 Correct 30 ms 1024 KB Correct.
4 Correct 30 ms 444 KB Correct.
5 Correct 31 ms 376 KB Correct.
6 Correct 10 ms 5920 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 39988 KB Correct.
2 Correct 181 ms 984 KB Correct.
3 Correct 166 ms 1036 KB Correct.
4 Correct 180 ms 1012 KB Correct.
5 Correct 192 ms 572 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 996 KB Correct.
2 Correct 29 ms 1004 KB Correct.
3 Correct 37 ms 992 KB Correct.
4 Correct 29 ms 6804 KB Correct.
5 Correct 33 ms 452 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 980 KB Correct.
2 Correct 29 ms 972 KB Correct.
3 Correct 59 ms 52128 KB Correct.
4 Correct 20 ms 4564 KB Correct.
5 Correct 33 ms 460 KB Correct.
6 Correct 28 ms 984 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 900 KB Correct.
2 Correct 33 ms 1364 KB Correct.
3 Correct 895 ms 46372 KB Correct.
4 Correct 397 ms 11972 KB Correct.
5 Correct 814 ms 27808 KB Correct.
6 Correct 295 ms 11356 KB Correct.
7 Correct 387 ms 12204 KB Correct.
8 Correct 308 ms 2392 KB Correct.
9 Correct 160 ms 1048 KB Correct.
10 Correct 150 ms 988 KB Correct.
11 Correct 290 ms 1072 KB Correct.
12 Correct 180 ms 1020 KB Correct.
13 Correct 172 ms 968 KB Correct.
14 Correct 362 ms 14892 KB Correct.
15 Correct 325 ms 4204 KB Correct.
16 Correct 169 ms 1044 KB Correct.
17 Correct 194 ms 1048 KB Correct.
18 Correct 166 ms 988 KB Correct.
19 Correct 442 ms 1040 KB Correct.
20 Correct 13 ms 416 KB Correct.
21 Correct 13 ms 904 KB Correct.
22 Correct 22 ms 1620 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 1620 KB Correct.
2 Correct 73 ms 2632 KB Correct.
3 Correct 1657 ms 131064 KB Correct.
4 Correct 429 ms 5440 KB Correct.
5 Correct 1589 ms 53072 KB Correct.
6 Correct 660 ms 18880 KB Correct.
7 Correct 684 ms 24344 KB Correct.
8 Correct 458 ms 2392 KB Correct.
9 Correct 372 ms 1732 KB Correct.
10 Correct 327 ms 1720 KB Correct.
11 Correct 299 ms 524 KB Correct.
12 Correct 402 ms 1724 KB Correct.
13 Correct 390 ms 1684 KB Correct.
14 Correct 1611 ms 51696 KB Correct.
15 Correct 1675 ms 65020 KB Correct.
16 Correct 668 ms 22068 KB Correct.
17 Correct 455 ms 5124 KB Correct.
18 Correct 375 ms 1696 KB Correct.
19 Correct 430 ms 1700 KB Correct.
20 Correct 373 ms 1648 KB Correct.
21 Correct 1004 ms 1792 KB Correct.
22 Correct 27 ms 492 KB Correct.
23 Correct 28 ms 1452 KB Correct.
24 Correct 46 ms 2448 KB Correct.