oj.uz

답안 #1112784

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1112784 2024-11-14T20:11:44 Z mariaclara 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 528 ms 27568 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[35];
    vector<vector<pii>> edges(N);
    vector<bool> vis(N);

    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 22 ms 848 KB Correct.
2 Correct 22 ms 520 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 804 KB Correct.
2 Correct 22 ms 1616 KB Correct.
3 Correct 20 ms 860 KB Correct.
4 Correct 21 ms 848 KB Correct.
5 Correct 24 ms 1616 KB Correct.
6 Correct 20 ms 3756 KB Correct.
7 Correct 25 ms 3664 KB Correct.
8 Correct 14 ms 7264 KB Correct.
9 Correct 23 ms 592 KB Correct.
10 Correct 23 ms 592 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 1584 KB Correct.
2 Correct 27 ms 864 KB Correct.
3 Correct 25 ms 860 KB Correct.
4 Correct 28 ms 656 KB Correct.
5 Correct 27 ms 660 KB Correct.
6 Correct 8 ms 3408 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 21004 KB Correct.
2 Correct 149 ms 1636 KB Correct.
3 Correct 134 ms 2148 KB Correct.
4 Correct 146 ms 1780 KB Correct.
5 Correct 98 ms 1396 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1616 KB Correct.
2 Correct 22 ms 1848 KB Correct.
3 Correct 24 ms 1952 KB Correct.
4 Correct 24 ms 4144 KB Correct.
5 Correct 25 ms 1360 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1836 KB Correct.
2 Correct 21 ms 1616 KB Correct.
3 Correct 47 ms 27568 KB Correct.
4 Correct 24 ms 3272 KB Correct.
5 Correct 25 ms 1552 KB Correct.
6 Correct 31 ms 1908 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 1856 KB Correct.
2 Correct 24 ms 1104 KB Correct.
3 Correct 377 ms 25308 KB Correct.
4 Correct 285 ms 8196 KB Correct.
5 Correct 528 ms 19916 KB Correct.
6 Correct 255 ms 10188 KB Correct.
7 Correct 289 ms 7200 KB Correct.
8 Correct 250 ms 2880 KB Correct.
9 Correct 137 ms 1824 KB Correct.
10 Correct 136 ms 1780 KB Correct.
11 Correct 238 ms 2616 KB Correct.
12 Correct 152 ms 1852 KB Correct.
13 Correct 158 ms 1880 KB Correct.
14 Correct 259 ms 9320 KB Correct.
15 Correct 267 ms 4212 KB Correct.
16 Correct 145 ms 1872 KB Correct.
17 Correct 173 ms 1952 KB Correct.
18 Correct 170 ms 1872 KB Correct.
19 Correct 435 ms 2716 KB Correct.
20 Correct 11 ms 592 KB Correct.
21 Correct 12 ms 716 KB Correct.
22 Correct 20 ms 1360 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -