Submission #1112805

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112805	2024-11-14T21:54:12 Z	mariaclara	Cyberland (APIO23_cyberland)	C++17	100 / 100	1786 ms	90928 KB

cyberland

#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[105];
    vector<vector<pii>> edges(N);
    vector<bool> vis(N);
    K = min(K, 100);

    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

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	592 KB	Correct.
2	Correct	24 ms	584 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	848 KB	Correct.
2	Correct	23 ms	840 KB	Correct.
3	Correct	35 ms	840 KB	Correct.
4	Correct	24 ms	848 KB	Correct.
5	Correct	22 ms	864 KB	Correct.
6	Correct	20 ms	3836 KB	Correct.
7	Correct	26 ms	3756 KB	Correct.
8	Correct	14 ms	7248 KB	Correct.
9	Correct	22 ms	652 KB	Correct.
10	Correct	23 ms	592 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	848 KB	Correct.
2	Correct	27 ms	864 KB	Correct.
3	Correct	26 ms	928 KB	Correct.
4	Correct	29 ms	592 KB	Correct.
5	Correct	29 ms	660 KB	Correct.
6	Correct	8 ms	3408 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	19988 KB	Correct.
2	Correct	155 ms	812 KB	Correct.
3	Correct	132 ms	848 KB	Correct.
4	Correct	142 ms	816 KB	Correct.
5	Correct	88 ms	592 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	848 KB	Correct.
2	Correct	21 ms	848 KB	Correct.
3	Correct	23 ms	944 KB	Correct.
4	Correct	21 ms	3376 KB	Correct.
5	Correct	21 ms	656 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	892 KB	Correct.
2	Correct	21 ms	848 KB	Correct.
3	Correct	45 ms	25672 KB	Correct.
4	Correct	16 ms	2768 KB	Correct.
5	Correct	26 ms	592 KB	Correct.
6	Correct	27 ms	956 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	176 ms	848 KB	Correct.
2	Correct	24 ms	848 KB	Correct.
3	Correct	379 ms	22836 KB	Correct.
4	Correct	307 ms	6160 KB	Correct.
5	Correct	587 ms	18164 KB	Correct.
6	Correct	255 ms	8660 KB	Correct.
7	Correct	308 ms	6076 KB	Correct.
8	Correct	264 ms	1332 KB	Correct.
9	Correct	141 ms	948 KB	Correct.
10	Correct	140 ms	780 KB	Correct.
11	Correct	235 ms	940 KB	Correct.
12	Correct	157 ms	840 KB	Correct.
13	Correct	154 ms	900 KB	Correct.
14	Correct	287 ms	7508 KB	Correct.
15	Correct	275 ms	2172 KB	Correct.
16	Correct	153 ms	828 KB	Correct.
17	Correct	174 ms	892 KB	Correct.
18	Correct	178 ms	836 KB	Correct.
19	Correct	436 ms	592 KB	Correct.
20	Correct	11 ms	592 KB	Correct.
21	Correct	12 ms	592 KB	Correct.
22	Correct	19 ms	1104 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	530 ms	2396 KB	Correct.
2	Correct	75 ms	1872 KB	Correct.
3	Correct	316 ms	90928 KB	Correct.
4	Correct	383 ms	5572 KB	Correct.
5	Correct	1786 ms	39548 KB	Correct.
6	Correct	791 ms	15804 KB	Correct.
7	Correct	766 ms	17488 KB	Correct.
8	Correct	441 ms	3340 KB	Correct.
9	Correct	422 ms	2408 KB	Correct.
10	Correct	423 ms	2220 KB	Correct.
11	Correct	152 ms	1608 KB	Correct.
12	Correct	447 ms	2432 KB	Correct.
13	Correct	462 ms	2436 KB	Correct.
14	Correct	1747 ms	37452 KB	Correct.
15	Correct	1349 ms	46140 KB	Correct.
16	Correct	552 ms	12796 KB	Correct.
17	Correct	440 ms	5484 KB	Correct.
18	Correct	438 ms	2364 KB	Correct.
19	Correct	552 ms	2576 KB	Correct.
20	Correct	504 ms	2448 KB	Correct.
21	Correct	1352 ms	3268 KB	Correct.
22	Correct	24 ms	592 KB	Correct.
23	Correct	34 ms	1256 KB	Correct.
24	Correct	53 ms	1872 KB	Correct.

Submission #1112805

Compilation message