oj.uz

Submission #975212

# Submission time Handle Problem Language Result Execution time Memory
975212 2024-05-04T14:57:47 Z ShaShi Cyberland (APIO23_cyberland) C++17
97 / 100
 1089 ms 93548 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 = 66;
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 21 ms 31448 KB Correct.
2 Correct 21 ms 31456 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31320 KB Correct.
2 Correct 29 ms 31324 KB Correct.
3 Correct 27 ms 31324 KB Correct.
4 Correct 29 ms 31324 KB Correct.
5 Correct 29 ms 31564 KB Correct.
6 Correct 27 ms 36188 KB Correct.
7 Correct 37 ms 36124 KB Correct.
8 Correct 24 ms 42956 KB Correct.
9 Correct 27 ms 31580 KB Correct.
10 Correct 26 ms 31324 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31520 KB Correct.
2 Correct 29 ms 31528 KB Correct.
3 Correct 29 ms 31324 KB Correct.
4 Correct 28 ms 31324 KB Correct.
5 Correct 27 ms 31324 KB Correct.
6 Correct 13 ms 36196 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 70080 KB Correct.
2 Correct 272 ms 31724 KB Correct.
3 Correct 249 ms 31948 KB Correct.
4 Correct 257 ms 31836 KB Correct.
5 Correct 211 ms 31480 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31580 KB Correct.
2 Correct 32 ms 31580 KB Correct.
3 Correct 26 ms 31576 KB Correct.
4 Correct 29 ms 36444 KB Correct.
5 Correct 24 ms 31456 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31580 KB Correct.
2 Correct 24 ms 31580 KB Correct.
3 Correct 56 ms 75348 KB Correct.
4 Correct 21 ms 36440 KB Correct.
5 Correct 26 ms 31324 KB Correct.
6 Correct 27 ms 31564 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 31960 KB Correct.
2 Correct 47 ms 32920 KB Correct.
3 Correct 570 ms 89384 KB Correct.
4 Correct 485 ms 43692 KB Correct.
5 Correct 1089 ms 89448 KB Correct.
6 Correct 561 ms 73896 KB Correct.
7 Correct 486 ms 45772 KB Correct.
8 Correct 470 ms 33872 KB Correct.
9 Correct 254 ms 32456 KB Correct.
10 Correct 250 ms 32092 KB Correct.
11 Correct 471 ms 32060 KB Correct.
12 Correct 262 ms 31960 KB Correct.
13 Correct 291 ms 32204 KB Correct.
14 Correct 395 ms 58568 KB Correct.
15 Correct 460 ms 38776 KB Correct.
16 Correct 252 ms 31960 KB Correct.
17 Correct 312 ms 32208 KB Correct.
18 Correct 318 ms 31960 KB Correct.
19 Correct 700 ms 32120 KB Correct.
20 Correct 26 ms 31576 KB Correct.
21 Correct 25 ms 31704 KB Correct.
22 Correct 47 ms 33996 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 882 ms 33536 KB Correct.
2 Correct 130 ms 37756 KB Correct.
3 Incorrect 508 ms 93548 KB Wrong Answer.
4 Halted 0 ms 0 KB -