oj.uz

Submission #805415

# Submission time Handle Problem Language Result Execution time Memory
805415 2023-08-03T16:31:03 Z Theo830 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 159192 KB 
            #include "cyberland.h"
            #include <bits/stdc++.h>
            using namespace std;
            #define f(i,a,b) for(int i = a;i < b;i++)
            #define ll int
            #define ii pair<ll,ll>
            #define id pair<double,ii>
            #define F first
            #define S second
            #define pb push_back
            priority_queue<id>pq;
            bool v[100005] = {0};
            double dist[100005][70];
            vector<vector<ii> >adj;
            ll H;
            void dfs(ll idx){
                v[idx] = 1;
                for(auto x:adj[idx]){
                    if(!v[x.F] && x.F != H){
                        dfs(x.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) {
                double ans;
                H = h;
              	k = min(k,69);
                adj.assign(n+5,vector<ii>());
                f(i,0,n){
                    v[i] = 0;
                    f(j,0,k+1){
                        dist[i][j] = 1e18;
                    }
                }
                f(i,0,m){
                    adj[x[i]].pb(ii(y[i],c[i]));
                    adj[y[i]].pb(ii(x[i],c[i]));
                }
                dfs(0);
                f(i,0,n){
                    if((arr[i] == 0 && v[i]) || i == 0){
                        pq.push(id(0,ii(i,0)));
                        dist[i][0] = 0;
                    }
                }
                ans = 1e18;
                while(!pq.empty()){
                    id f = pq.top();
                    pq.pop();
                    double w = -f.F;
                    ll u = f.S.F;
                    ll ek = f.S.S;
                    if(dist[u][ek] < w){
                        continue;
                    }
                    if(arr[u] == 2 && ek+1 <= k){
                        for(auto x:adj[u]){
                            if(x.F == h){
                                ans = min(ans,dist[u][ek]/(double)2 + (double)x.S);
                            }
                            else if(dist[x.F][ek+1] > dist[u][ek]/(double)2 + (double)x.S){
                                dist[x.F][ek+1] = dist[u][ek]/(double)2 + (double)x.S;
                                pq.push(id(-dist[x.F][ek+1],ii(x.F,ek+1)));
                            }
                        }
                    }
                    for(auto x:adj[u]){
                        if(x.F == h){
                            ans = min(ans,dist[u][ek] + x.S);
                        }
                        else if(dist[x.F][ek] > dist[u][ek] + x.S){
                            dist[x.F][ek] = dist[u][ek] + x.S;
                            pq.push(id(-dist[x.F][ek],ii(x.F,ek)));
                        }
                    }
                }
                if(ans == 1e18){
                    ans = -1;
                }
                return ans;
            }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB Correct.
2 Correct 19 ms 468 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 956 KB Correct.
2 Correct 23 ms 1032 KB Correct.
3 Correct 22 ms 1004 KB Correct.
4 Correct 23 ms 1000 KB Correct.
5 Correct 22 ms 1064 KB Correct.
6 Correct 21 ms 6616 KB Correct.
7 Correct 27 ms 6516 KB Correct.
8 Correct 15 ms 12936 KB Correct.
9 Correct 21 ms 340 KB Correct.
10 Correct 20 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1012 KB Correct.
2 Correct 23 ms 1036 KB Correct.
3 Correct 29 ms 980 KB Correct.
4 Correct 22 ms 436 KB Correct.
5 Correct 21 ms 424 KB Correct.
6 Correct 6 ms 5588 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 39816 KB Correct.
2 Correct 250 ms 1168 KB Correct.
3 Correct 219 ms 1172 KB Correct.
4 Correct 233 ms 1100 KB Correct.
5 Correct 188 ms 560 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 980 KB Correct.
2 Correct 21 ms 980 KB Correct.
3 Correct 23 ms 1032 KB Correct.
4 Correct 22 ms 6740 KB Correct.
5 Correct 18 ms 424 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1052 KB Correct.
2 Correct 19 ms 980 KB Correct.
3 Correct 46 ms 48772 KB Correct.
4 Correct 15 ms 4948 KB Correct.
5 Correct 23 ms 416 KB Correct.
6 Correct 21 ms 1104 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 1552 KB Correct.
2 Correct 33 ms 2580 KB Correct.
3 Correct 608 ms 63460 KB Correct.
4 Correct 492 ms 14556 KB Correct.
5 Correct 907 ms 58856 KB Correct.
6 Correct 393 ms 26924 KB Correct.
7 Correct 485 ms 15984 KB Correct.
8 Correct 470 ms 2768 KB Correct.
9 Correct 218 ms 1516 KB Correct.
10 Correct 219 ms 2048 KB Correct.
11 Correct 468 ms 1400 KB Correct.
12 Correct 233 ms 1488 KB Correct.
13 Correct 262 ms 1472 KB Correct.
14 Correct 373 ms 31112 KB Correct.
15 Correct 469 ms 8628 KB Correct.
16 Correct 232 ms 1484 KB Correct.
17 Correct 270 ms 1408 KB Correct.
18 Correct 261 ms 1488 KB Correct.
19 Correct 646 ms 1484 KB Correct.
20 Correct 17 ms 596 KB Correct.
21 Correct 20 ms 1108 KB Correct.
22 Correct 29 ms 3456 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 2992 KB Correct.
2 Correct 109 ms 3524 KB Correct.
3 Correct 602 ms 66972 KB Correct.
4 Correct 974 ms 7468 KB Correct.
5 Execution timed out 3077 ms 159192 KB Time limit exceeded
6 Halted 0 ms 0 KB -