oj.uz

답안 #905087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
905087 2024-01-12T14:25:48 Z Fake4Fun 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 110 ms 15624 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
 
#define ll long long
#define pa pair<ll, int>
#define fi first
#define se second
using namespace std;
const int maxN = 1e5;
const double oo = 1e18, eps = 1e-7;
int n, fin;
short abi[maxN];
vector<pa> adj[maxN];
ll dist[maxN];
bool mini(ll &a, ll b) {
    if (a > b || a == -1) {
        a = b;
        return true;
    }
    return false;
}
void Dijkstra(int start) {
    for (int i = 0; i < n; i++) dist[i] = -1;
    priority_queue<pa, vector<pa>, greater<pa> > pq;
    dist[start] = 0; pq.emplace(0, start);
    ll D; int node;
    while (!pq.empty()) {
        tie(D, node) = pq.top(); pq.pop();
        if (D != dist[node]) continue;
        for (pa o : adj[node])
            if (mini(dist[o.se], D + o.fi) && o.se != fin) pq.emplace(dist[o.se], o.se);
    }
}
double rDist[2][maxN];
void Ford_Bellman(vector<int> &v) {
    queue<pair<double, int> > q;
    for (int x : v) {
        rDist[0][x] = rDist[1][x];
        q.emplace(rDist[0][x], x);
    }
    double D; int node;
    while (!q.empty()) {
        tie(D, node) = q.front(); q.pop();
        if (D > rDist[0][node]) continue;
        for (pa o : adj[node]) {
            if (o.se == fin) continue;
            if (abi[o.se] == 2) rDist[1][o.se] = min(rDist[1][o.se], (D + o.fi) / 2);
            if (rDist[0][o.se] > D + o.fi + eps) {
                rDist[0][o.se] = D + o.fi;
                q.emplace(rDist[0][o.se], o.se);
            }
        }
    }
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    n = N; fin = H;
    for (int i = 0; i < n; i++) {
        adj[i].clear();
        abi[i] = arr[i];
    }
    for (int i = 0; i < M; i++) {
        adj[x[i]].emplace_back(c[i], y[i]);
        adj[y[i]].emplace_back(c[i], x[i]);
    }
    Dijkstra(0);
    if (dist[fin] == -1) return -1;
    vector<int> posGo;
    posGo.push_back(0);
    for (int i = 0; i < n; i++)
        if (!abi[i] && dist[i] != -1) posGo.push_back(i);
    Dijkstra(fin);
    fill(rDist[0], rDist[0] + n, oo);
    fill(rDist[1], rDist[1] + n, oo);
    double ans = oo;
    for (int i : posGo) {
        ans = min(ans, (double)dist[i]);
        rDist[1][i] = 0;
    }
    // Travel 1st time
    Ford_Bellman(posGo);
    // Update posGo
    posGo.clear();
    for (int i = 0; i < n; i++)
        if (abi[i] == 2 && rDist[1][i] < oo) posGo.push_back(i);
    // Travel K-1 times
    K = min(K, 70); /// important;
    for (int t = 2; t <= K; t++) Ford_Bellman(posGo);
    for (int i : posGo) ans = min(ans, rDist[1][i] + dist[i]);
    return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 4952 KB Correct.
2 Correct 22 ms 5212 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 4956 KB Correct.
2 Correct 25 ms 6236 KB Correct.
3 Correct 24 ms 5992 KB Correct.
4 Correct 27 ms 5972 KB Correct.
5 Correct 24 ms 5980 KB Correct.
6 Correct 24 ms 6748 KB Correct.
7 Correct 28 ms 7032 KB Correct.
8 Correct 15 ms 7260 KB Correct.
9 Correct 23 ms 5932 KB Correct.
10 Correct 22 ms 5928 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 4956 KB Correct.
2 Correct 30 ms 5972 KB Correct.
3 Correct 26 ms 5980 KB Correct.
4 Correct 24 ms 5724 KB Correct.
5 Correct 24 ms 5724 KB Correct.
6 Correct 7 ms 5896 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 9812 KB Correct.
2 Correct 23 ms 5980 KB Correct.
3 Correct 22 ms 5980 KB Correct.
4 Correct 22 ms 5980 KB Correct.
5 Correct 23 ms 5724 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 5208 KB Correct.
2 Correct 22 ms 6236 KB Correct.
3 Correct 24 ms 6228 KB Correct.
4 Correct 23 ms 7276 KB Correct.
5 Correct 19 ms 5724 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 5212 KB Correct.
2 Correct 19 ms 5980 KB Correct.
3 Correct 35 ms 13404 KB Correct.
4 Correct 16 ms 6520 KB Correct.
5 Correct 20 ms 5724 KB Correct.
6 Correct 21 ms 6236 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 5208 KB Correct.
2 Correct 6 ms 5212 KB Correct.
3 Correct 107 ms 15592 KB Correct.
4 Correct 67 ms 9616 KB Correct.
5 Correct 79 ms 13932 KB Correct.
6 Correct 49 ms 12756 KB Correct.
7 Correct 62 ms 9300 KB Correct.
8 Correct 53 ms 7252 KB Correct.
9 Correct 23 ms 6236 KB Correct.
10 Correct 25 ms 6236 KB Correct.
11 Correct 52 ms 7000 KB Correct.
12 Correct 25 ms 6228 KB Correct.
13 Correct 26 ms 6236 KB Correct.
14 Correct 86 ms 11156 KB Correct.
15 Correct 72 ms 8276 KB Correct.
16 Correct 25 ms 6228 KB Correct.
17 Correct 27 ms 6236 KB Correct.
18 Correct 28 ms 6228 KB Correct.
19 Correct 52 ms 6996 KB Correct.
20 Correct 4 ms 4956 KB Correct.
21 Correct 5 ms 4956 KB Correct.
22 Correct 6 ms 5724 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 5208 KB Correct.
2 Correct 6 ms 5240 KB Correct.
3 Correct 73 ms 15624 KB Correct.
4 Correct 60 ms 7928 KB Correct.
5 Correct 110 ms 13952 KB Correct.
6 Correct 73 ms 12664 KB Correct.
7 Correct 81 ms 11276 KB Correct.
8 Correct 59 ms 7252 KB Correct.
9 Correct 29 ms 6016 KB Correct.
10 Correct 26 ms 6228 KB Correct.
11 Correct 81 ms 6228 KB Correct.
12 Correct 33 ms 6236 KB Correct.
13 Correct 30 ms 6236 KB Correct.
14 Correct 110 ms 12732 KB Correct.
15 Correct 100 ms 11376 KB Correct.
16 Correct 79 ms 9300 KB Correct.
17 Correct 58 ms 7428 KB Correct.
18 Correct 28 ms 6236 KB Correct.
19 Correct 32 ms 6296 KB Correct.
20 Correct 30 ms 6288 KB Correct.
21 Correct 63 ms 6996 KB Correct.
22 Correct 4 ms 4956 KB Correct.
23 Correct 4 ms 4956 KB Correct.
24 Correct 6 ms 5724 KB Correct.