oj.uz

Submission #975124

# Submission time Handle Problem Language Result Execution time Memory
975124 2024-05-04T13:19:30 Z ShaShi Cyberland (APIO23_cyberland) C++17
97 / 100
 1129 ms 81308 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 = 33;
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 = 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 27 ms 29428 KB Correct.
2 Correct 23 ms 29784 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 29488 KB Correct.
2 Correct 33 ms 29528 KB Correct.
3 Correct 29 ms 29444 KB Correct.
4 Correct 35 ms 29276 KB Correct.
5 Correct 29 ms 29276 KB Correct.
6 Correct 34 ms 32092 KB Correct.
7 Correct 41 ms 32092 KB Correct.
8 Correct 21 ms 36956 KB Correct.
9 Correct 28 ms 29408 KB Correct.
10 Correct 37 ms 29276 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 29276 KB Correct.
2 Correct 31 ms 30268 KB Correct.
3 Correct 36 ms 30460 KB Correct.
4 Correct 31 ms 30392 KB Correct.
5 Correct 32 ms 30180 KB Correct.
6 Correct 12 ms 32168 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 54428 KB Correct.
2 Correct 277 ms 30724 KB Correct.
3 Correct 271 ms 30580 KB Correct.
4 Correct 261 ms 30548 KB Correct.
5 Correct 224 ms 30316 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 29556 KB Correct.
2 Correct 31 ms 29532 KB Correct.
3 Correct 28 ms 29528 KB Correct.
4 Correct 29 ms 32344 KB Correct.
5 Correct 26 ms 29272 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 29532 KB Correct.
2 Correct 27 ms 30416 KB Correct.
3 Correct 65 ms 58704 KB Correct.
4 Correct 25 ms 32860 KB Correct.
5 Correct 28 ms 30120 KB Correct.
6 Correct 31 ms 30296 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 29908 KB Correct.
2 Correct 49 ms 30676 KB Correct.
3 Correct 619 ms 67352 KB Correct.
4 Correct 550 ms 39700 KB Correct.
5 Correct 1093 ms 81308 KB Correct.
6 Correct 562 ms 70372 KB Correct.
7 Correct 478 ms 39756 KB Correct.
8 Correct 495 ms 33804 KB Correct.
9 Correct 263 ms 30940 KB Correct.
10 Correct 256 ms 30972 KB Correct.
11 Correct 475 ms 31828 KB Correct.
12 Correct 266 ms 30924 KB Correct.
13 Correct 284 ms 31180 KB Correct.
14 Correct 397 ms 50396 KB Correct.
15 Correct 460 ms 36676 KB Correct.
16 Correct 253 ms 30928 KB Correct.
17 Correct 310 ms 30988 KB Correct.
18 Correct 301 ms 31180 KB Correct.
19 Correct 697 ms 31676 KB Correct.
20 Correct 27 ms 29776 KB Correct.
21 Correct 25 ms 29788 KB Correct.
22 Correct 46 ms 31976 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1129 ms 31452 KB Wrong Answer.
2 Halted 0 ms 0 KB -