oj.uz

답안 #975131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975131 2024-05-04T13:26:17 Z ShaShi 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 189100 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 = 70;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 31576 KB Correct.
2 Correct 28 ms 31580 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 31480 KB Correct.
2 Correct 32 ms 31492 KB Correct.
3 Correct 30 ms 31324 KB Correct.
4 Correct 31 ms 31488 KB Correct.
5 Correct 32 ms 31540 KB Correct.
6 Correct 31 ms 36120 KB Correct.
7 Correct 46 ms 36176 KB Correct.
8 Correct 29 ms 45064 KB Correct.
9 Correct 27 ms 31356 KB Correct.
10 Correct 28 ms 31448 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 31508 KB Correct.
2 Correct 33 ms 31324 KB Correct.
3 Correct 30 ms 31320 KB Correct.
4 Correct 34 ms 31448 KB Correct.
5 Correct 36 ms 31324 KB Correct.
6 Correct 14 ms 36184 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 76736 KB Correct.
2 Correct 289 ms 31760 KB Correct.
3 Correct 242 ms 31836 KB Correct.
4 Correct 259 ms 31836 KB Correct.
5 Correct 222 ms 31500 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 31580 KB Correct.
2 Correct 37 ms 31580 KB Correct.
3 Correct 35 ms 31572 KB Correct.
4 Correct 32 ms 36336 KB Correct.
5 Correct 31 ms 31324 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 31592 KB Correct.
2 Correct 27 ms 31576 KB Correct.
3 Correct 74 ms 81512 KB Correct.
4 Correct 25 ms 36444 KB Correct.
5 Correct 27 ms 31320 KB Correct.
6 Correct 31 ms 31856 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 287 ms 31948 KB Correct.
2 Correct 45 ms 32720 KB Correct.
3 Correct 617 ms 97632 KB Correct.
4 Correct 500 ms 45828 KB Correct.
5 Correct 1066 ms 90816 KB Correct.
6 Correct 520 ms 74668 KB Correct.
7 Correct 468 ms 47820 KB Correct.
8 Correct 484 ms 33940 KB Correct.
9 Correct 266 ms 32460 KB Correct.
10 Correct 250 ms 31952 KB Correct.
11 Correct 475 ms 31828 KB Correct.
12 Correct 267 ms 31956 KB Correct.
13 Correct 280 ms 31952 KB Correct.
14 Correct 410 ms 62648 KB Correct.
15 Correct 461 ms 38800 KB Correct.
16 Correct 260 ms 32140 KB Correct.
17 Correct 309 ms 31972 KB Correct.
18 Correct 304 ms 32220 KB Correct.
19 Correct 691 ms 31960 KB Correct.
20 Correct 28 ms 31600 KB Correct.
21 Correct 28 ms 31704 KB Correct.
22 Correct 45 ms 33864 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 947 ms 33584 KB Correct.
2 Correct 128 ms 36348 KB Correct.
3 Correct 639 ms 101900 KB Correct.
4 Correct 1000 ms 34860 KB Correct.
5 Execution timed out 3057 ms 189100 KB Time limit exceeded
6 Halted 0 ms 0 KB -