oj.uz

Submission #975129

# Submission time Handle Problem Language Result Execution time Memory
975129 2024-05-04T13:25:24 Z ShaShi Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 193660 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 = 80;
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 29272 KB Correct.
2 Correct 23 ms 29276 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31320 KB Correct.
2 Correct 36 ms 31324 KB Correct.
3 Correct 31 ms 31320 KB Correct.
4 Correct 33 ms 31324 KB Correct.
5 Correct 32 ms 31576 KB Correct.
6 Correct 42 ms 36180 KB Correct.
7 Correct 52 ms 36224 KB Correct.
8 Correct 27 ms 45088 KB Correct.
9 Correct 27 ms 31320 KB Correct.
10 Correct 29 ms 31324 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 31504 KB Correct.
2 Correct 33 ms 31320 KB Correct.
3 Correct 36 ms 31324 KB Correct.
4 Correct 30 ms 31320 KB Correct.
5 Correct 30 ms 31324 KB Correct.
6 Correct 13 ms 36188 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 79044 KB Correct.
2 Correct 305 ms 31872 KB Correct.
3 Correct 241 ms 31824 KB Correct.
4 Correct 257 ms 31840 KB Correct.
5 Correct 216 ms 31512 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31580 KB Correct.
2 Correct 36 ms 31548 KB Correct.
3 Correct 31 ms 31576 KB Correct.
4 Correct 35 ms 36444 KB Correct.
5 Correct 26 ms 31324 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31576 KB Correct.
2 Correct 28 ms 31580 KB Correct.
3 Correct 86 ms 89688 KB Correct.
4 Correct 27 ms 36444 KB Correct.
5 Correct 30 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 291 ms 32004 KB Correct.
2 Correct 50 ms 32724 KB Correct.
3 Correct 640 ms 103880 KB Correct.
4 Correct 507 ms 47820 KB Correct.
5 Correct 1117 ms 94448 KB Correct.
6 Correct 580 ms 75688 KB Correct.
7 Correct 471 ms 49912 KB Correct.
8 Correct 489 ms 34068 KB Correct.
9 Correct 252 ms 32456 KB Correct.
10 Correct 253 ms 32088 KB Correct.
11 Correct 482 ms 31796 KB Correct.
12 Correct 276 ms 31960 KB Correct.
13 Correct 284 ms 31944 KB Correct.
14 Correct 410 ms 68796 KB Correct.
15 Correct 473 ms 38804 KB Correct.
16 Correct 259 ms 31964 KB Correct.
17 Correct 310 ms 31980 KB Correct.
18 Correct 303 ms 31956 KB Correct.
19 Correct 714 ms 31956 KB Correct.
20 Correct 28 ms 31568 KB Correct.
21 Correct 27 ms 31704 KB Correct.
22 Correct 47 ms 34000 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1085 ms 33760 KB Correct.
2 Correct 148 ms 36188 KB Correct.
3 Correct 706 ms 112388 KB Correct.
4 Correct 1098 ms 37048 KB Correct.
5 Execution timed out 3047 ms 193660 KB Time limit exceeded
6 Halted 0 ms 0 KB -