Submission #1112784

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112784	2024-11-14T20:11:44 Z	mariaclara	Cyberland (APIO23_cyberland)	C++17	97 / 100	528 ms	27568 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[35];
    vector<vector<pii>> edges(N);
    vector<bool> vis(N);

    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	22 ms	848 KB	Correct.
2	Correct	22 ms	520 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	804 KB	Correct.
2	Correct	22 ms	1616 KB	Correct.
3	Correct	20 ms	860 KB	Correct.
4	Correct	21 ms	848 KB	Correct.
5	Correct	24 ms	1616 KB	Correct.
6	Correct	20 ms	3756 KB	Correct.
7	Correct	25 ms	3664 KB	Correct.
8	Correct	14 ms	7264 KB	Correct.
9	Correct	23 ms	592 KB	Correct.
10	Correct	23 ms	592 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	1584 KB	Correct.
2	Correct	27 ms	864 KB	Correct.
3	Correct	25 ms	860 KB	Correct.
4	Correct	28 ms	656 KB	Correct.
5	Correct	27 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	138 ms	21004 KB	Correct.
2	Correct	149 ms	1636 KB	Correct.
3	Correct	134 ms	2148 KB	Correct.
4	Correct	146 ms	1780 KB	Correct.
5	Correct	98 ms	1396 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	1616 KB	Correct.
2	Correct	22 ms	1848 KB	Correct.
3	Correct	24 ms	1952 KB	Correct.
4	Correct	24 ms	4144 KB	Correct.
5	Correct	25 ms	1360 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	1836 KB	Correct.
2	Correct	21 ms	1616 KB	Correct.
3	Correct	47 ms	27568 KB	Correct.
4	Correct	24 ms	3272 KB	Correct.
5	Correct	25 ms	1552 KB	Correct.
6	Correct	31 ms	1908 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	179 ms	1856 KB	Correct.
2	Correct	24 ms	1104 KB	Correct.
3	Correct	377 ms	25308 KB	Correct.
4	Correct	285 ms	8196 KB	Correct.
5	Correct	528 ms	19916 KB	Correct.
6	Correct	255 ms	10188 KB	Correct.
7	Correct	289 ms	7200 KB	Correct.
8	Correct	250 ms	2880 KB	Correct.
9	Correct	137 ms	1824 KB	Correct.
10	Correct	136 ms	1780 KB	Correct.
11	Correct	238 ms	2616 KB	Correct.
12	Correct	152 ms	1852 KB	Correct.
13	Correct	158 ms	1880 KB	Correct.
14	Correct	259 ms	9320 KB	Correct.
15	Correct	267 ms	4212 KB	Correct.
16	Correct	145 ms	1872 KB	Correct.
17	Correct	173 ms	1952 KB	Correct.
18	Correct	170 ms	1872 KB	Correct.
19	Correct	435 ms	2716 KB	Correct.
20	Correct	11 ms	592 KB	Correct.
21	Correct	12 ms	716 KB	Correct.
22	Correct	20 ms	1360 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	4 ms	860 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Submission #1112784

Compilation message