oj.uz

Submission #975138

# Submission time Handle Problem Language Result Execution time Memory
975138 2024-05-04T13:29:10 Z ShaShi Cyberland (APIO23_cyberland) C++17
97 / 100
 1066 ms 91516 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 = 65;
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 29272 KB Correct.
2 Correct 21 ms 29276 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31324 KB Correct.
2 Correct 30 ms 31324 KB Correct.
3 Correct 28 ms 31324 KB Correct.
4 Correct 29 ms 31324 KB Correct.
5 Correct 33 ms 31324 KB Correct.
6 Correct 30 ms 36184 KB Correct.
7 Correct 43 ms 36136 KB Correct.
8 Correct 20 ms 41052 KB Correct.
9 Correct 26 ms 29276 KB Correct.
10 Correct 27 ms 29276 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31324 KB Correct.
2 Correct 30 ms 31320 KB Correct.
3 Correct 28 ms 31576 KB Correct.
4 Correct 28 ms 29396 KB Correct.
5 Correct 28 ms 29412 KB Correct.
6 Correct 12 ms 34136 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 68692 KB Correct.
2 Correct 282 ms 31724 KB Correct.
3 Correct 245 ms 31836 KB Correct.
4 Correct 265 ms 31980 KB Correct.
5 Correct 213 ms 29272 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31580 KB Correct.
2 Correct 28 ms 31580 KB Correct.
3 Correct 32 ms 31580 KB Correct.
4 Correct 29 ms 36400 KB Correct.
5 Correct 24 ms 29276 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31576 KB Correct.
2 Correct 25 ms 31580 KB Correct.
3 Correct 58 ms 73300 KB Correct.
4 Correct 21 ms 34648 KB Correct.
5 Correct 26 ms 29276 KB Correct.
6 Correct 28 ms 31544 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 32004 KB Correct.
2 Correct 46 ms 32724 KB Correct.
3 Correct 605 ms 87320 KB Correct.
4 Correct 505 ms 43972 KB Correct.
5 Correct 1066 ms 87140 KB Correct.
6 Correct 588 ms 75036 KB Correct.
7 Correct 464 ms 43728 KB Correct.
8 Correct 469 ms 31656 KB Correct.
9 Correct 252 ms 32456 KB Correct.
10 Correct 250 ms 32208 KB Correct.
11 Correct 464 ms 31828 KB Correct.
12 Correct 264 ms 31952 KB Correct.
13 Correct 279 ms 31948 KB Correct.
14 Correct 401 ms 58548 KB Correct.
15 Correct 454 ms 36728 KB Correct.
16 Correct 258 ms 32192 KB Correct.
17 Correct 306 ms 31992 KB Correct.
18 Correct 306 ms 31956 KB Correct.
19 Correct 691 ms 32096 KB Correct.
20 Correct 26 ms 29528 KB Correct.
21 Correct 26 ms 31700 KB Correct.
22 Correct 48 ms 34016 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 33760 KB Correct.
2 Correct 128 ms 36800 KB Correct.
3 Incorrect 527 ms 91516 KB Wrong Answer.
4 Halted 0 ms 0 KB -