oj.uz

답안 #1112805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1112805 2024-11-14T21:54:12 Z mariaclara 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 1786 ms 90928 KB 
#include "cyberland.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,double,int> trio;
const int MAXN = 2e5 + 5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair 
#define pb push_back 
#define fr first
#define sc second

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    vector<double> dist[105];
    vector<vector<pii>> edges(N);
    vector<bool> vis(N);
    K = min(K, 100);

    for(int i = 0; i <= K; i++) dist[i].resize(N, 1e18);
    
    for(int i = 0; i < M; i++) {
        edges[x[i]].pb({y[i], c[i]});
        edges[y[i]].pb({x[i], c[i]});
    }

    priority_queue<trio> pq;
    pq.push({K, 0, 0});
    
    queue<int> fila;
    fila.push(0);

    while(!fila.empty()) {
        int x = fila.front();
        fila.pop();

        if(x == H) continue;
        if(arr[x] == 0) pq.push({K, 0, x});

        for(auto [viz, peso] : edges[x])
            if(!vis[viz]) fila.push(viz), vis[viz] = 1;
    }

    for(int i = 0; i < N; i++) vis[i] = 0;

    while(!pq.empty()) {
        auto [k, D, at] = pq.top();
        pq.pop();
        D *= -1;
        if(arr[at] == 0) D = 0; 

        if(dist[k][at] < D) continue;
        if(at == H) continue;

        for(auto [viz, peso] : edges[at]) {
            if(D + peso < dist[k][viz])
                pq.push({k, - D - peso, viz}), dist[k][viz] = D + peso;

            if(k >= 1 and arr[at] == 2 and D/2 + peso < dist[k-1][viz]) 
                pq.push({k-1, -D/2 -peso, viz}), dist[k-1][viz] = D/2 + peso;
        }
    }
    
    double ans = 1e18;

    for(int i = 0; i <= K; i++)
        ans = min(ans, dist[i][H]);
    
    if(ans == 1e18) return -1;
    return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 592 KB Correct.
2 Correct 24 ms 584 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 848 KB Correct.
2 Correct 23 ms 840 KB Correct.
3 Correct 35 ms 840 KB Correct.
4 Correct 24 ms 848 KB Correct.
5 Correct 22 ms 864 KB Correct.
6 Correct 20 ms 3836 KB Correct.
7 Correct 26 ms 3756 KB Correct.
8 Correct 14 ms 7248 KB Correct.
9 Correct 22 ms 652 KB Correct.
10 Correct 23 ms 592 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 848 KB Correct.
2 Correct 27 ms 864 KB Correct.
3 Correct 26 ms 928 KB Correct.
4 Correct 29 ms 592 KB Correct.
5 Correct 29 ms 660 KB Correct.
6 Correct 8 ms 3408 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 19988 KB Correct.
2 Correct 155 ms 812 KB Correct.
3 Correct 132 ms 848 KB Correct.
4 Correct 142 ms 816 KB Correct.
5 Correct 88 ms 592 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 848 KB Correct.
2 Correct 21 ms 848 KB Correct.
3 Correct 23 ms 944 KB Correct.
4 Correct 21 ms 3376 KB Correct.
5 Correct 21 ms 656 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 892 KB Correct.
2 Correct 21 ms 848 KB Correct.
3 Correct 45 ms 25672 KB Correct.
4 Correct 16 ms 2768 KB Correct.
5 Correct 26 ms 592 KB Correct.
6 Correct 27 ms 956 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 848 KB Correct.
2 Correct 24 ms 848 KB Correct.
3 Correct 379 ms 22836 KB Correct.
4 Correct 307 ms 6160 KB Correct.
5 Correct 587 ms 18164 KB Correct.
6 Correct 255 ms 8660 KB Correct.
7 Correct 308 ms 6076 KB Correct.
8 Correct 264 ms 1332 KB Correct.
9 Correct 141 ms 948 KB Correct.
10 Correct 140 ms 780 KB Correct.
11 Correct 235 ms 940 KB Correct.
12 Correct 157 ms 840 KB Correct.
13 Correct 154 ms 900 KB Correct.
14 Correct 287 ms 7508 KB Correct.
15 Correct 275 ms 2172 KB Correct.
16 Correct 153 ms 828 KB Correct.
17 Correct 174 ms 892 KB Correct.
18 Correct 178 ms 836 KB Correct.
19 Correct 436 ms 592 KB Correct.
20 Correct 11 ms 592 KB Correct.
21 Correct 12 ms 592 KB Correct.
22 Correct 19 ms 1104 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 530 ms 2396 KB Correct.
2 Correct 75 ms 1872 KB Correct.
3 Correct 316 ms 90928 KB Correct.
4 Correct 383 ms 5572 KB Correct.
5 Correct 1786 ms 39548 KB Correct.
6 Correct 791 ms 15804 KB Correct.
7 Correct 766 ms 17488 KB Correct.
8 Correct 441 ms 3340 KB Correct.
9 Correct 422 ms 2408 KB Correct.
10 Correct 423 ms 2220 KB Correct.
11 Correct 152 ms 1608 KB Correct.
12 Correct 447 ms 2432 KB Correct.
13 Correct 462 ms 2436 KB Correct.
14 Correct 1747 ms 37452 KB Correct.
15 Correct 1349 ms 46140 KB Correct.
16 Correct 552 ms 12796 KB Correct.
17 Correct 440 ms 5484 KB Correct.
18 Correct 438 ms 2364 KB Correct.
19 Correct 552 ms 2576 KB Correct.
20 Correct 504 ms 2448 KB Correct.
21 Correct 1352 ms 3268 KB Correct.
22 Correct 24 ms 592 KB Correct.
23 Correct 34 ms 1256 KB Correct.
24 Correct 53 ms 1872 KB Correct.