Submission #979606

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
979606	2024-05-11T08:15:30 Z	phoenix0423	Cyberland (APIO23_cyberland)	C++17	100 / 100	999 ms	82212 KB

cyberland

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#include "cyberland.h"
const int maxn = 2e5 + 5;
const double INF = 1e18;
const double eps = 1e-9;
vector<pll> adj[maxn];
int vis[maxn];
double dist[maxn][81];
int ed = 0;

void dfs(int pos){
    vis[pos] = 1;
    if(pos == ed) return;
    for(auto [x, w] : adj[pos]){
        if(vis[x]) continue;
        dfs(x);
    }
}
 
struct info{
    double d;
    int pos, l;
    info(){}
    info(double _d, int _pos, int _l) : d(_d), pos(_pos), l(_l){}
    bool operator > (const info& other) const{
        if(l != other.l) return l > other.l;
        return d > other.d;
    }
};
 
priority_queue<info, vector<info>, greater<info>> q;
 
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) {
    k = min(k, 80);
    ed = h;
    for(int i = 0; i < n; i++) adj[i].clear(), vis[i] = 0;
    for(int i = 0; i < m; i++){
        adj[x[i]].pb({y[i], c[i]});
        adj[y[i]].pb({x[i], c[i]});
    }
    dfs(0);
    if(!vis[h]) return -1;
    for(int i = 1; i < n; i++) for(int j = 0; j <= k; j++) dist[i][j] = INF;
    arr[0] = 0;
    for(int i = 0; i < n; i++){
        if(arr[i] == 0 && vis[i]){
            for(int j = 0; j <= k; j++) dist[i][j] = 0;
            q.push(info(0, i, 0));
        }
    }
    q.push(info(0, 0, 0));
    while(!q.empty()){
        auto [d, pos, l] = q.top(); q.pop();
        if(dist[pos][l] < d || pos == h) continue;
        for(auto [x, w] : adj[pos]){
            if(dist[x][l] > d + w){
                dist[x][l] = d + w;
                q.push(info(dist[x][l], x, l));
            }
        }
        if(arr[pos] == 2 && l < k){
            d /= 2, l++;
            if(dist[pos][l] < d) continue;
            for(auto [x, w] : adj[pos]){
                if(dist[x][l] > d + w){
                    dist[x][l] = d + w;
                    q.push(info(dist[x][l], x, l));
                }
            }
        }
    }
    double ans = INF;
    for(int i = 0; i <= k; i++) ans = min(ans, dist[h][i]);
    return ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	7516 KB	Correct.
2	Correct	14 ms	7516 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	9816 KB	Correct.
2	Correct	25 ms	9772 KB	Correct.
3	Correct	20 ms	9820 KB	Correct.
4	Correct	21 ms	9564 KB	Correct.
5	Correct	21 ms	9820 KB	Correct.
6	Correct	19 ms	14428 KB	Correct.
7	Correct	24 ms	14428 KB	Correct.
8	Correct	13 ms	21512 KB	Correct.
9	Correct	20 ms	7516 KB	Correct.
10	Correct	19 ms	7528 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	9564 KB	Correct.
2	Correct	22 ms	9768 KB	Correct.
3	Correct	25 ms	9820 KB	Correct.
4	Correct	21 ms	7512 KB	Correct.
5	Correct	21 ms	7512 KB	Correct.
6	Correct	6 ms	14420 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	49492 KB	Correct.
2	Correct	65 ms	9820 KB	Correct.
3	Correct	56 ms	9788 KB	Correct.
4	Correct	58 ms	9756 KB	Correct.
5	Correct	40 ms	7260 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	9816 KB	Correct.
2	Correct	19 ms	9820 KB	Correct.
3	Correct	19 ms	9860 KB	Correct.
4	Correct	22 ms	14936 KB	Correct.
5	Correct	16 ms	7516 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	9820 KB	Correct.
2	Correct	17 ms	9820 KB	Correct.
3	Correct	32 ms	13904 KB	Correct.
4	Correct	15 ms	12636 KB	Correct.
5	Correct	19 ms	7524 KB	Correct.
6	Correct	18 ms	9816 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	9828 KB	Correct.
2	Correct	12 ms	9820 KB	Correct.
3	Correct	519 ms	77536 KB	Correct.
4	Correct	204 ms	24064 KB	Correct.
5	Correct	235 ms	38100 KB	Correct.
6	Correct	109 ms	22224 KB	Correct.
7	Correct	202 ms	26048 KB	Correct.
8	Correct	167 ms	10068 KB	Correct.
9	Correct	54 ms	9816 KB	Correct.
10	Correct	50 ms	9924 KB	Correct.
11	Correct	154 ms	9824 KB	Correct.
12	Correct	60 ms	9904 KB	Correct.
13	Correct	61 ms	9820 KB	Correct.
14	Correct	201 ms	42840 KB	Correct.
15	Correct	185 ms	16852 KB	Correct.
16	Correct	60 ms	9820 KB	Correct.
17	Correct	67 ms	9872 KB	Correct.
18	Correct	61 ms	9820 KB	Correct.
19	Correct	146 ms	9564 KB	Correct.
20	Correct	5 ms	7256 KB	Correct.
21	Correct	6 ms	9560 KB	Correct.
22	Correct	10 ms	10332 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	137 ms	9812 KB	Correct.
2	Correct	24 ms	9816 KB	Correct.
3	Correct	740 ms	82212 KB	Correct.
4	Correct	251 ms	12516 KB	Correct.
5	Correct	568 ms	38092 KB	Correct.
6	Correct	260 ms	22300 KB	Correct.
7	Correct	399 ms	34128 KB	Correct.
8	Correct	244 ms	9812 KB	Correct.
9	Correct	113 ms	9920 KB	Correct.
10	Correct	104 ms	9856 KB	Correct.
11	Correct	103 ms	7780 KB	Correct.
12	Correct	126 ms	9896 KB	Correct.
13	Correct	131 ms	10112 KB	Correct.
14	Correct	999 ms	38200 KB	Correct.
15	Correct	857 ms	44856 KB	Correct.
16	Correct	333 ms	21844 KB	Correct.
17	Correct	259 ms	12124 KB	Correct.
18	Correct	119 ms	9928 KB	Correct.
19	Correct	140 ms	9852 KB	Correct.
20	Correct	131 ms	9868 KB	Correct.
21	Correct	319 ms	9768 KB	Correct.
22	Correct	8 ms	7260 KB	Correct.
23	Correct	10 ms	9564 KB	Correct.
24	Correct	20 ms	10332 KB	Correct.

Submission #979606

Compilation message