oj.uz

답안 #983948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
983948 2024-05-16T08:23:02 Z hariaakas646 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 1037 ms 2097152 KB 
#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;


vector<vii> graph;
vb vis;

void dfs(int x) {
    if(vis[x]) return;
    vis[x] = true;
    for(auto e : graph[x]) dfs(e.f);
}

double solve(int n, int m, int k, int h, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    graph = vector<vii>(n);
    frange(i, m) {
        int a=x[i];int b = y[i];
        if(a != h) graph[a].pb(mp(b, c[i]));
        if(b != h) graph[b].pb(mp(a, c[i]));
    }
    vis = vb(n);
    dfs(0);
    vector<vector<ld>> dist(k+1, vector<ld>(n, 1e15));
    vector<vb> vis2(k+1, vb(n));
    dist[0][0] = 0;
    priority_queue<pair<int, pair<ld, int>>> pq;
    pq.push(mp(0, mp(0, 0)));
    forr(i, 1, n) {
        if(vis[i] && arr[i] == 0) {
            dist[0][i] = 0;
            pq.push(mp(0, mp(0, i)));
        }
    }

    while(pq.size()) {
        auto p = pq.top();
        pq.pop();
        int x = p.s.s;
        int c = -p.f;
        ld w = -p.s.f;
        if(vis2[c][x]) continue;
        vis2[c][x] = true;

        for(auto e : graph[x]) {
            if(dist[c][e.f] > w + e.s) {
                dist[c][e.f] = w + e.s;
                pq.push(mp(-c, mp(-dist[c][e.f], e.f)));
            }
            if(c<k && arr[e.f]==2 && dist[c+1][e.f] > ld(w+e.s)/2) {
                dist[c+1][e.f] = ld(w+e.s)/2;
                pq.push(mp(-c-1, mp(-dist[c+1][e.f], e.f)));
            }
        }
    }

    ld mi = 1e15;
    frange(i, k+1) mi = min(mi, dist[i][h]);
    if(abs(mi-1e15)<=1) return -1;
    else
    return mi;


}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 564 KB Correct.
2 Correct 42 ms 772 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 1104 KB Correct.
2 Correct 30 ms 1036 KB Correct.
3 Correct 29 ms 1028 KB Correct.
4 Correct 31 ms 1068 KB Correct.
5 Correct 30 ms 1060 KB Correct.
6 Correct 27 ms 6364 KB Correct.
7 Correct 38 ms 6180 KB Correct.
8 Correct 19 ms 12124 KB Correct.
9 Correct 31 ms 600 KB Correct.
10 Correct 27 ms 604 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 1048 KB Correct.
2 Correct 33 ms 1068 KB Correct.
3 Correct 29 ms 1140 KB Correct.
4 Correct 30 ms 604 KB Correct.
5 Correct 29 ms 600 KB Correct.
6 Correct 7 ms 5468 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 35780 KB Correct.
2 Correct 189 ms 1116 KB Correct.
3 Correct 157 ms 1064 KB Correct.
4 Correct 197 ms 1444 KB Correct.
5 Correct 110 ms 604 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 1040 KB Correct.
2 Correct 28 ms 1032 KB Correct.
3 Correct 28 ms 1032 KB Correct.
4 Correct 27 ms 6284 KB Correct.
5 Correct 24 ms 604 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 1132 KB Correct.
2 Correct 25 ms 1248 KB Correct.
3 Correct 46 ms 45272 KB Correct.
4 Correct 20 ms 4328 KB Correct.
5 Correct 27 ms 740 KB Correct.
6 Correct 27 ms 1032 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 1080 KB Correct.
2 Correct 28 ms 1368 KB Correct.
3 Correct 535 ms 37548 KB Correct.
4 Correct 359 ms 9980 KB Correct.
5 Correct 629 ms 29216 KB Correct.
6 Correct 291 ms 11628 KB Correct.
7 Correct 358 ms 9904 KB Correct.
8 Correct 324 ms 2240 KB Correct.
9 Correct 169 ms 1280 KB Correct.
10 Correct 160 ms 1032 KB Correct.
11 Correct 278 ms 1092 KB Correct.
12 Correct 178 ms 1080 KB Correct.
13 Correct 178 ms 1072 KB Correct.
14 Correct 328 ms 10764 KB Correct.
15 Correct 323 ms 4380 KB Correct.
16 Correct 177 ms 1116 KB Correct.
17 Correct 201 ms 1100 KB Correct.
18 Correct 213 ms 1128 KB Correct.
19 Correct 519 ms 1100 KB Correct.
20 Correct 11 ms 604 KB Correct.
21 Correct 13 ms 916 KB Correct.
22 Correct 23 ms 1628 KB Correct.

Subtask #8
0.0 / 3.0

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