oj.uz

Submission #975211

# Submission time Handle Problem Language Result Execution time Memory
975211 2024-05-04T14:56:55 Z ShaShi Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 187104 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 = 67;
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];
bool seen[MAXN], sn[MAXN][K];
vector<pii> adj[MAXN];
vector<int> source;
priority_queue<pair<double, pii>, vector<pair<double, pii> >, greater<pair<double, pii> > > pq;
 
 
 
void DFS(int v) {
    seen[v] = 1;
    
    if (v == 0 || arr[v] == 0) source.pb(v);
 
    for (auto cur:adj[v]) {
        int u = cur.F, w = cur.S;
 
        if (!seen[u]) DFS(u);
    }
}
 
 
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();
    source.clear();
    fill(seen, seen+n+1, 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];
 
    seen[h] = 1;
    DFS(0);
 
    for (int s:source) {
        dp[s][0] = 0;
        pq.push(mp(0, mp(s, 0)));
    }
 
    while (pq.size()) {
        auto cur = pq.top().S; pq.pop();
 
        v = cur.F;
        tmp = cur.S;
 
        for (auto cur:adj[v]) {
            int u = cur.F, w = cur.S;
 
            if (dp[u][tmp] > dp[v][tmp]+w) {
                dp[u][tmp] = dp[v][tmp]+w;
 
                if (u != h) pq.push(mp(dp[u][tmp], mp(u, tmp)));
            }
 
            if (arr[u] == 2 && tmp+1 <= k && dp[u][tmp+1] > (dp[v][tmp]+w)/2.0) {
                dp[u][tmp+1] = (dp[v][tmp]+w)/2.0;
 
                if (u != h) pq.push(mp(dp[u][tmp+1], mp(u, tmp+1)));
            }
        }
    }
 
    double res = INF;
 
    for (int i=0; i<=k; i++) res = min(res, dp[h][i]);
 
    return (res == INF? -1 : res);
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 29788 KB Correct.
2 Correct 22 ms 29732 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 32592 KB Correct.
2 Correct 29 ms 32600 KB Correct.
3 Correct 28 ms 32348 KB Correct.
4 Correct 29 ms 32336 KB Correct.
5 Correct 29 ms 32336 KB Correct.
6 Correct 28 ms 36956 KB Correct.
7 Correct 36 ms 37380 KB Correct.
8 Correct 22 ms 41424 KB Correct.
9 Correct 26 ms 30296 KB Correct.
10 Correct 26 ms 30288 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 32336 KB Correct.
2 Correct 30 ms 32348 KB Correct.
3 Correct 28 ms 32348 KB Correct.
4 Correct 28 ms 30292 KB Correct.
5 Correct 28 ms 30300 KB Correct.
6 Correct 13 ms 34396 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 70620 KB Correct.
2 Correct 276 ms 33000 KB Correct.
3 Correct 238 ms 32460 KB Correct.
4 Correct 256 ms 32600 KB Correct.
5 Correct 213 ms 30488 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 32344 KB Correct.
2 Correct 28 ms 32600 KB Correct.
3 Correct 27 ms 32604 KB Correct.
4 Correct 29 ms 37408 KB Correct.
5 Correct 24 ms 30044 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32600 KB Correct.
2 Correct 25 ms 32316 KB Correct.
3 Correct 62 ms 77244 KB Correct.
4 Correct 22 ms 34904 KB Correct.
5 Correct 26 ms 30300 KB Correct.
6 Correct 26 ms 32340 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 32820 KB Correct.
2 Correct 48 ms 32720 KB Correct.
3 Correct 611 ms 91776 KB Correct.
4 Correct 477 ms 46028 KB Correct.
5 Correct 1071 ms 88512 KB Correct.
6 Correct 563 ms 75948 KB Correct.
7 Correct 465 ms 45652 KB Correct.
8 Correct 474 ms 33876 KB Correct.
9 Correct 272 ms 32984 KB Correct.
10 Correct 251 ms 32960 KB Correct.
11 Correct 472 ms 33700 KB Correct.
12 Correct 264 ms 32856 KB Correct.
13 Correct 281 ms 32972 KB Correct.
14 Correct 398 ms 60644 KB Correct.
15 Correct 462 ms 38804 KB Correct.
16 Correct 257 ms 33136 KB Correct.
17 Correct 310 ms 32968 KB Correct.
18 Correct 301 ms 32968 KB Correct.
19 Correct 703 ms 33792 KB Correct.
20 Correct 25 ms 29784 KB Correct.
21 Correct 25 ms 31836 KB Correct.
22 Correct 49 ms 34000 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 887 ms 34100 KB Correct.
2 Correct 126 ms 37944 KB Correct.
3 Correct 528 ms 96336 KB Correct.
4 Correct 963 ms 37056 KB Correct.
5 Execution timed out 3029 ms 187104 KB Time limit exceeded
6 Halted 0 ms 0 KB -