oj.uz

Submission #975126

# Submission time Handle Problem Language Result Execution time Memory
975126 2024-05-04T13:21:13 Z ShaShi Cyberland (APIO23_cyberland) C++17
97 / 100
 1094 ms 78812 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 = 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 24 ms 29272 KB Correct.
2 Correct 29 ms 29428 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 29276 KB Correct.
2 Correct 30 ms 29304 KB Correct.
3 Correct 29 ms 29276 KB Correct.
4 Correct 31 ms 29276 KB Correct.
5 Correct 29 ms 29272 KB Correct.
6 Correct 29 ms 32092 KB Correct.
7 Correct 37 ms 32132 KB Correct.
8 Correct 23 ms 36816 KB Correct.
9 Correct 33 ms 29276 KB Correct.
10 Correct 27 ms 29272 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 29276 KB Correct.
2 Correct 30 ms 29444 KB Correct.
3 Correct 30 ms 29532 KB Correct.
4 Correct 30 ms 29276 KB Correct.
5 Correct 31 ms 29276 KB Correct.
6 Correct 12 ms 32088 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 56004 KB Correct.
2 Correct 278 ms 29832 KB Correct.
3 Correct 244 ms 29720 KB Correct.
4 Correct 265 ms 29788 KB Correct.
5 Correct 222 ms 29700 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 29528 KB Correct.
2 Correct 28 ms 29528 KB Correct.
3 Correct 28 ms 29532 KB Correct.
4 Correct 33 ms 32320 KB Correct.
5 Correct 25 ms 29276 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 29532 KB Correct.
2 Correct 28 ms 29532 KB Correct.
3 Correct 57 ms 57080 KB Correct.
4 Correct 23 ms 32220 KB Correct.
5 Correct 26 ms 29276 KB Correct.
6 Correct 27 ms 29532 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 30020 KB Correct.
2 Correct 47 ms 30676 KB Correct.
3 Correct 612 ms 64828 KB Correct.
4 Correct 485 ms 37544 KB Correct.
5 Correct 1094 ms 78812 KB Correct.
6 Correct 536 ms 69040 KB Correct.
7 Correct 468 ms 37728 KB Correct.
8 Correct 485 ms 31764 KB Correct.
9 Correct 253 ms 30312 KB Correct.
10 Correct 253 ms 29904 KB Correct.
11 Correct 479 ms 29764 KB Correct.
12 Correct 264 ms 29924 KB Correct.
13 Correct 285 ms 30164 KB Correct.
14 Correct 391 ms 48364 KB Correct.
15 Correct 469 ms 34676 KB Correct.
16 Correct 254 ms 29916 KB Correct.
17 Correct 311 ms 30188 KB Correct.
18 Correct 301 ms 29908 KB Correct.
19 Correct 689 ms 29912 KB Correct.
20 Correct 27 ms 29532 KB Correct.
21 Correct 29 ms 29708 KB Correct.
22 Correct 48 ms 31820 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 29996 KB Correct.
2 Correct 53 ms 30624 KB Correct.
3 Incorrect 257 ms 71588 KB Wrong Answer.
4 Halted 0 ms 0 KB -