oj.uz

답안 #751887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
751887 2023-06-01T17:30:47 Z aryan12 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 93180 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5, K = 68;
double dist[K][N];
vector<pair<int, int> > g[N];
bool vis[N], source[N];
int a[N], H;
 
void dfs(int node)
{
    vis[node] = true;
    if(a[node] == 0)
    {
        source[node] = true;
    }
    if(node == H)
    {
        return;
    }
    for(auto [to, wt]: g[node])
    {
        if(!vis[to])
        {
            dfs(to);
        }
    }
}
 
double solve(int n, int m, int k, int h, 
    vector<int> x, vector<int> y, vector<int> c, 
    vector<int> arr) 
{
    H = h;
    k = min(k, 67);
    for(int i = 0; i <= n; i++)
    {
        source[i] = false;
        vis[i] = false;
        if(i != n) a[i] = arr[i];
        g[i].clear();
        for(int j = 0; j <= k; j++)
        {
            dist[j][i] = 1e18;
        }
    }
    for(int i = 0; i < m; i++)
    {
        g[x[i]].push_back({y[i], c[i]});
        g[y[i]].push_back({x[i], c[i]});
    }
    dfs(0);
    source[0] = true;
    if(!vis[H])
    {
        return -1;
    }
    priority_queue<pair<double, int> > pq;
    for(int i = 0; i < n; i++)
    {
        // cout << "source[i] = " << source[i] << "\n";
        if(source[i])
        {
            pq.push({0, i});
            dist[0][i] = 0;
        }
    }
    while(!pq.empty())
    {
        auto [dis, p] = pq.top();
        pq.pop();
        int cur_k = p / 100000, node = p % 100000;
        dis = -dis;
        if(dist[cur_k][node] < dis || node == h)
        {
            continue;
        }
        for(auto [to, wt]: g[node])
        {
            if(a[to] == 0) continue;
            double wt_d = wt;
            if(dist[cur_k][to] > dist[cur_k][node] + wt_d)
            {
                dist[cur_k][to] = dist[cur_k][node] + wt_d;
                pq.push({-dist[cur_k][to], to + 100000 * cur_k});
            }
            if(a[to] == 1 || cur_k == k) continue;
            if(dist[cur_k + 1][to] > (dist[cur_k][node] + wt_d) / 2.0)
            {
                dist[cur_k + 1][to] = (dist[cur_k][node] + wt_d) / 2.0;
                pq.push({-dist[cur_k + 1][to], to + 100000 * (cur_k + 1)});
            }
        }
    }
    double ans = 1e18;
    // for(int i = 0; i < n; i++)
    // {
    //     for(int j = 0; j <= k; j++)
    //     {
    //         cout << "dist[" << i << "][" << j << "] = " << dist[i][j] << "\n";
    //     }
    // }
    for(int i = 0; i <= k; i++)
    {
        ans = min(ans, dist[i][h]);
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 2980 KB Correct.
2 Correct 23 ms 2996 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 3188 KB Correct.
2 Correct 27 ms 3196 KB Correct.
3 Correct 34 ms 3228 KB Correct.
4 Correct 24 ms 3156 KB Correct.
5 Correct 29 ms 3200 KB Correct.
6 Correct 33 ms 5984 KB Correct.
7 Correct 34 ms 5968 KB Correct.
8 Correct 22 ms 9112 KB Correct.
9 Correct 25 ms 2928 KB Correct.
10 Correct 33 ms 2924 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 3220 KB Correct.
2 Correct 26 ms 3228 KB Correct.
3 Correct 29 ms 3240 KB Correct.
4 Correct 35 ms 2900 KB Correct.
5 Correct 35 ms 2900 KB Correct.
6 Correct 10 ms 5480 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 23496 KB Correct.
2 Correct 257 ms 3432 KB Correct.
3 Correct 185 ms 3400 KB Correct.
4 Correct 179 ms 3396 KB Correct.
5 Correct 157 ms 2928 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 3268 KB Correct.
2 Correct 28 ms 3268 KB Correct.
3 Correct 22 ms 3292 KB Correct.
4 Correct 27 ms 6156 KB Correct.
5 Correct 21 ms 2904 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 3256 KB Correct.
2 Correct 21 ms 3288 KB Correct.
3 Correct 64 ms 26668 KB Correct.
4 Correct 24 ms 5364 KB Correct.
5 Correct 25 ms 2900 KB Correct.
6 Correct 22 ms 3316 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 3780 KB Correct.
2 Correct 34 ms 4392 KB Correct.
3 Correct 775 ms 25628 KB Correct.
4 Correct 559 ms 9372 KB Correct.
5 Correct 912 ms 49836 KB Correct.
6 Correct 403 ms 26024 KB Correct.
7 Correct 544 ms 9112 KB Correct.
8 Correct 492 ms 4096 KB Correct.
9 Correct 174 ms 3996 KB Correct.
10 Correct 167 ms 4140 KB Correct.
11 Correct 488 ms 3532 KB Correct.
12 Correct 199 ms 4120 KB Correct.
13 Correct 223 ms 4052 KB Correct.
14 Correct 455 ms 12728 KB Correct.
15 Correct 518 ms 6196 KB Correct.
16 Correct 177 ms 4052 KB Correct.
17 Correct 211 ms 3824 KB Correct.
18 Correct 198 ms 3732 KB Correct.
19 Correct 430 ms 3716 KB Correct.
20 Correct 20 ms 3016 KB Correct.
21 Correct 14 ms 3452 KB Correct.
22 Correct 32 ms 5704 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 666 ms 5692 KB Correct.
2 Correct 95 ms 7164 KB Correct.
3 Correct 609 ms 65888 KB Correct.
4 Correct 1185 ms 7804 KB Correct.
5 Execution timed out 3044 ms 93180 KB Time limit exceeded
6 Halted 0 ms 0 KB -