oj.uz

Submission #975250

# Submission time Handle Problem Language Result Execution time Memory
975250 2024-05-04T15:47:08 Z ShaShi Cyberland (APIO23_cyberland) C++17
100 / 100
 157 ms 92104 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define mp make_pair
#define F first
#define S second


using namespace std;

typedef long long ll;


const int MAXN = (int)1e6 + 7;
const int K = 70;
const int MOD = 998244353;
const double INF = (double)1e18 + 7;


int n, m, k, h, tmp, tmp2, tmp3, tmp4, ans, u, v, w;
int arr[MAXN];
double dp[MAXN][K], p2[K];
bool seen[MAXN], sn[MAXN][K];
vector<pii> adj[MAXN];
priority_queue<pair<double, pii>, vector<pair<double, pii> >, greater<pair<double, pii> > > pq;



void DFS(int v) {
    seen[v] = 1;
    
    for (auto cur:adj[v]) {
        int u = cur.F, w = cur.S;

        if (!seen[u] && u != h) DFS(u);
    }
}



inline void relax(int v, int x, double d) {
    if (dp[v][x] > d) {
        dp[v][x] = d;
        pq.push(mp(d, mp(v, x)));
    }
}


double solve(int N, int M, int kk, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> A) {
    n = N; m = M; k = min(K-1, kk); h = H;

    for (int i=0; i<n; i++) adj[i].clear();
    fill(seen, seen+n+1, 0);

    while (pq.size()) pq.pop();

    p2[0] = 1.0;
    for (int i=1; i<K; i++) p2[i] = p2[i-1]/2.0;

    for (int j=0; j<=k; j++) for (int i=0; i<n; i++) dp[i][j] = INF;

    for (int i=0; i<m; i++) {
        u = x[i]; v = y[i]; w = c[i];

        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
    }

    for (int i=0; i<n; i++) arr[i] = A[i];

    DFS(0);
    
    relax(h, k, 0);

    while (pq.size()) {
        auto cur = pq.top(); pq.pop();

        v = cur.S.F;
        tmp = cur.S.S;

        if (dp[v][tmp] < cur.F) continue;
        if ((arr[v] == 0 && seen[v]) || v == 0) return cur.F;

        for (auto cur:adj[v]) {
            int u = cur.F;
            double w = cur.S;
            
            if (!seen[u]) continue;
            
            relax(u, tmp, dp[v][tmp] + w*p2[k-tmp]);

            if (arr[v] == 2 && tmp > 0) relax(u, tmp-1, dp[v][tmp] + w*p2[k-tmp+1]);
        }
    }
    
    return -1;
}

Compilation message

cyberland.cpp: In function 'void DFS(int)':
cyberland.cpp:35:24: warning: unused variable 'w' [-Wunused-variable]
   35 |         int u = cur.F, w = cur.S;
      |                        ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31320 KB Correct.
2 Correct 20 ms 31836 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31320 KB Correct.
2 Correct 25 ms 32604 KB Correct.
3 Correct 24 ms 32520 KB Correct.
4 Correct 23 ms 32344 KB Correct.
5 Correct 23 ms 32348 KB Correct.
6 Correct 22 ms 37056 KB Correct.
7 Correct 26 ms 37212 KB Correct.
8 Correct 16 ms 43356 KB Correct.
9 Correct 24 ms 32348 KB Correct.
10 Correct 26 ms 32544 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31576 KB Correct.
2 Correct 23 ms 32348 KB Correct.
3 Correct 21 ms 32344 KB Correct.
4 Correct 25 ms 32208 KB Correct.
5 Correct 24 ms 32312 KB Correct.
6 Correct 10 ms 36184 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 66128 KB Correct.
2 Correct 22 ms 31324 KB Correct.
3 Correct 22 ms 32508 KB Correct.
4 Correct 22 ms 32348 KB Correct.
5 Correct 24 ms 32348 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31580 KB Correct.
2 Correct 25 ms 32604 KB Correct.
3 Correct 29 ms 32600 KB Correct.
4 Correct 26 ms 37204 KB Correct.
5 Correct 23 ms 32092 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31576 KB Correct.
2 Correct 22 ms 31580 KB Correct.
3 Correct 49 ms 77392 KB Correct.
4 Correct 19 ms 36188 KB Correct.
5 Correct 26 ms 31616 KB Correct.
6 Correct 22 ms 32348 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31380 KB Correct.
2 Correct 9 ms 31576 KB Correct.
3 Correct 56 ms 88520 KB Correct.
4 Correct 43 ms 45376 KB Correct.
5 Correct 41 ms 56660 KB Correct.
6 Correct 32 ms 41008 KB Correct.
7 Correct 44 ms 47544 KB Correct.
8 Correct 43 ms 35840 KB Correct.
9 Correct 23 ms 32348 KB Correct.
10 Correct 22 ms 32336 KB Correct.
11 Correct 42 ms 33372 KB Correct.
12 Correct 23 ms 32604 KB Correct.
13 Correct 23 ms 32464 KB Correct.
14 Correct 46 ms 61168 KB Correct.
15 Correct 43 ms 40528 KB Correct.
16 Correct 23 ms 32592 KB Correct.
17 Correct 24 ms 32604 KB Correct.
18 Correct 24 ms 32592 KB Correct.
19 Correct 41 ms 33364 KB Correct.
20 Correct 9 ms 31580 KB Correct.
21 Correct 8 ms 31324 KB Correct.
22 Correct 9 ms 31836 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 31616 KB Correct.
2 Correct 9 ms 31580 KB Correct.
3 Correct 90 ms 92104 KB Correct.
4 Correct 41 ms 36092 KB Correct.
5 Correct 44 ms 56760 KB Correct.
6 Correct 36 ms 41312 KB Correct.
7 Correct 48 ms 55120 KB Correct.
8 Correct 43 ms 33624 KB Correct.
9 Correct 24 ms 32596 KB Correct.
10 Correct 25 ms 32348 KB Correct.
11 Correct 157 ms 32652 KB Correct.
12 Correct 25 ms 32604 KB Correct.
13 Correct 28 ms 32592 KB Correct.
14 Correct 55 ms 58264 KB Correct.
15 Correct 55 ms 63492 KB Correct.
16 Correct 44 ms 43004 KB Correct.
17 Correct 55 ms 35668 KB Correct.
18 Correct 25 ms 32604 KB Correct.
19 Correct 25 ms 32600 KB Correct.
20 Correct 25 ms 32636 KB Correct.
21 Correct 42 ms 33364 KB Correct.
22 Correct 9 ms 31324 KB Correct.
23 Correct 8 ms 31324 KB Correct.
24 Correct 10 ms 31856 KB Correct.