oj.uz

Submission #975127

# Submission time Handle Problem Language Result Execution time Memory
975127 2024-05-04T13:23:08 Z ShaShi Cyberland (APIO23_cyberland) C++17
97 / 100
 1057 ms 99828 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 = 62;
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, sn[i][j] = 0;

    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;


        // if (sn[v][tmp]) continue;
        // sn[v][tmp] = 1;

        if (v == h) continue;


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

            if (dp[u][tmp] > dp[v][tmp]+w) {
				// cout << "@" << v << " " << tmp << " " << u << " : " << dp[v][tmp]+w << endl;
                dp[u][tmp] = dp[v][tmp]+w;
                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;

				// cout << "@" << v << " " << tmp << " " << u << " : " << dp[u][tmp+1] << endl;

                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 28 ms 31320 KB Correct.
2 Correct 24 ms 31552 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31320 KB Correct.
2 Correct 39 ms 31348 KB Correct.
3 Correct 30 ms 31324 KB Correct.
4 Correct 32 ms 31500 KB Correct.
5 Correct 31 ms 31324 KB Correct.
6 Correct 31 ms 36188 KB Correct.
7 Correct 39 ms 36244 KB Correct.
8 Correct 23 ms 43112 KB Correct.
9 Correct 29 ms 31484 KB Correct.
10 Correct 30 ms 31576 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 31324 KB Correct.
2 Correct 31 ms 31324 KB Correct.
3 Correct 32 ms 31528 KB Correct.
4 Correct 31 ms 31468 KB Correct.
5 Correct 36 ms 31580 KB Correct.
6 Correct 13 ms 36188 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 75820 KB Correct.
2 Correct 275 ms 31828 KB Correct.
3 Correct 239 ms 31832 KB Correct.
4 Correct 257 ms 31836 KB Correct.
5 Correct 216 ms 31572 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31600 KB Correct.
2 Correct 34 ms 31576 KB Correct.
3 Correct 29 ms 31580 KB Correct.
4 Correct 31 ms 36444 KB Correct.
5 Correct 25 ms 31324 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31580 KB Correct.
2 Correct 27 ms 31580 KB Correct.
3 Correct 70 ms 79464 KB Correct.
4 Correct 25 ms 36444 KB Correct.
5 Correct 28 ms 31320 KB Correct.
6 Correct 29 ms 31580 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 31960 KB Correct.
2 Correct 45 ms 32720 KB Correct.
3 Correct 665 ms 93640 KB Correct.
4 Correct 483 ms 43792 KB Correct.
5 Correct 1057 ms 89040 KB Correct.
6 Correct 570 ms 73096 KB Correct.
7 Correct 472 ms 47820 KB Correct.
8 Correct 478 ms 33940 KB Correct.
9 Correct 255 ms 32368 KB Correct.
10 Correct 251 ms 31952 KB Correct.
11 Correct 481 ms 31832 KB Correct.
12 Correct 264 ms 31980 KB Correct.
13 Correct 286 ms 31960 KB Correct.
14 Correct 397 ms 62668 KB Correct.
15 Correct 471 ms 38612 KB Correct.
16 Correct 257 ms 31964 KB Correct.
17 Correct 309 ms 31960 KB Correct.
18 Correct 302 ms 31956 KB Correct.
19 Correct 717 ms 31960 KB Correct.
20 Correct 27 ms 31580 KB Correct.
21 Correct 26 ms 31760 KB Correct.
22 Correct 47 ms 34000 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 33516 KB Correct.
2 Correct 113 ms 37120 KB Correct.
3 Incorrect 492 ms 99828 KB Wrong Answer.
4 Halted 0 ms 0 KB -