Submission #905087

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
905087	2024-01-12T14:25:48 Z	Fake4Fun	Cyberland (APIO23_cyberland)	C++17	100 / 100	110 ms	15624 KB

cyberland

#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

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	4952 KB	Correct.
2	Correct	22 ms	5212 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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.

Submission #905087

Compilation message