Submission #983948

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
983948	2024-05-16T08:23:02 Z	hariaakas646	Cyberland (APIO23_cyberland)	C++17	97 / 100	1037 ms	2097152 KB

cyberland

#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

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	564 KB	Correct.
2	Correct	42 ms	772 KB	Correct.

Subtask #2
8.0 / 8.0

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

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

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

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

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

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

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1037 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Submission #983948

Compilation message