oj.uz

Submission #805402

# Submission time Handle Problem Language Result Execution time Memory
805402 2023-08-03T16:23:28 Z Theo830 Cyberland (APIO23_cyberland) C++17
97 / 100
 967 ms 59304 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 long long
    #define ii pair<ll,ll>
    #define id pair<double,ll>
    #define F first
    #define S second
    #define pb push_back
    priority_queue<id,vector<id>,greater<id> >pq;
    bool v[100005] = {0};
    double dist[100005][55];
    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;
        adj.assign(n+5,vector<ii>());
        k = min(k,50);
        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,(k+1) * i));
                dist[i][0] = 0;
            }
        }
        ans = 1e18;
        while(!pq.empty()){
            id f = pq.top();
            pq.pop();
            double w = f.F;
            ll u = f.S / (k+1);
            ll ek = f.S % (k+1);
            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],(k+1) * 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],(k+1) * x.F + ek));
                }
            }
        }
        if(ans == 1e18){
            ans = -1;
        }
        return ans;
    }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 468 KB Correct.
2 Correct 15 ms 468 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 912 KB Correct.
2 Correct 22 ms 916 KB Correct.
3 Correct 21 ms 932 KB Correct.
4 Correct 22 ms 920 KB Correct.
5 Correct 26 ms 932 KB Correct.
6 Correct 24 ms 5648 KB Correct.
7 Correct 32 ms 5504 KB Correct.
8 Correct 15 ms 10852 KB Correct.
9 Correct 19 ms 420 KB Correct.
10 Correct 19 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 852 KB Correct.
2 Correct 23 ms 896 KB Correct.
3 Correct 21 ms 952 KB Correct.
4 Correct 22 ms 424 KB Correct.
5 Correct 21 ms 428 KB Correct.
6 Correct 6 ms 4820 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 33988 KB Correct.
2 Correct 255 ms 1088 KB Correct.
3 Correct 226 ms 1044 KB Correct.
4 Correct 244 ms 1132 KB Correct.
5 Correct 194 ms 428 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 980 KB Correct.
2 Correct 23 ms 868 KB Correct.
3 Correct 21 ms 948 KB Correct.
4 Correct 22 ms 5716 KB Correct.
5 Correct 17 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 972 KB Correct.
2 Correct 18 ms 852 KB Correct.
3 Correct 55 ms 41220 KB Correct.
4 Correct 14 ms 4480 KB Correct.
5 Correct 19 ms 340 KB Correct.
6 Correct 20 ms 992 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 1404 KB Correct.
2 Correct 38 ms 2368 KB Correct.
3 Correct 590 ms 53692 KB Correct.
4 Correct 488 ms 12384 KB Correct.
5 Correct 967 ms 56380 KB Correct.
6 Correct 389 ms 27444 KB Correct.
7 Correct 481 ms 13524 KB Correct.
8 Correct 497 ms 2460 KB Correct.
9 Correct 219 ms 1404 KB Correct.
10 Correct 221 ms 1996 KB Correct.
11 Correct 491 ms 1280 KB Correct.
12 Correct 235 ms 1460 KB Correct.
13 Correct 252 ms 1504 KB Correct.
14 Correct 429 ms 26376 KB Correct.
15 Correct 473 ms 7480 KB Correct.
16 Correct 242 ms 1360 KB Correct.
17 Correct 277 ms 1436 KB Correct.
18 Correct 271 ms 1380 KB Correct.
19 Correct 658 ms 1456 KB Correct.
20 Correct 18 ms 596 KB Correct.
21 Correct 18 ms 1108 KB Correct.
22 Correct 29 ms 3576 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 1892 KB Correct.
2 Correct 66 ms 3576 KB Correct.
3 Incorrect 400 ms 59304 KB Wrong Answer.
4 Halted 0 ms 0 KB -