oj.uz

Submission #805398

# Submission time Handle Problem Language Result Execution time Memory
805398 2023-08-03T16:22:35 Z Theo830 Cyberland (APIO23_cyberland) C++17
97 / 100
 881 ms 59812 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][60];
    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;
        if(k <= 30){
            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));
                    }
                }
            }
        }
        else{
            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 == 0){
                    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] > (double)x.S){
                            dist[x.F][ek+1] = (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 15 ms 724 KB Correct.
2 Correct 15 ms 672 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1836 KB Correct.
2 Correct 23 ms 1960 KB Correct.
3 Correct 22 ms 1868 KB Correct.
4 Correct 24 ms 1992 KB Correct.
5 Correct 29 ms 1960 KB Correct.
6 Correct 22 ms 6820 KB Correct.
7 Correct 28 ms 7052 KB Correct.
8 Correct 16 ms 12120 KB Correct.
9 Correct 21 ms 1272 KB Correct.
10 Correct 21 ms 1292 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1960 KB Correct.
2 Correct 23 ms 1876 KB Correct.
3 Correct 22 ms 1872 KB Correct.
4 Correct 22 ms 1304 KB Correct.
5 Correct 26 ms 1260 KB Correct.
6 Correct 6 ms 5332 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 37556 KB Correct.
2 Correct 257 ms 2164 KB Correct.
3 Correct 226 ms 2100 KB Correct.
4 Correct 240 ms 1960 KB Correct.
5 Correct 196 ms 1364 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1840 KB Correct.
2 Correct 24 ms 1980 KB Correct.
3 Correct 22 ms 2016 KB Correct.
4 Correct 23 ms 7124 KB Correct.
5 Correct 19 ms 1168 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1880 KB Correct.
2 Correct 19 ms 1824 KB Correct.
3 Correct 47 ms 46068 KB Correct.
4 Correct 15 ms 5396 KB Correct.
5 Correct 21 ms 1300 KB Correct.
6 Correct 22 ms 2004 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 2408 KB Correct.
2 Correct 34 ms 2640 KB Correct.
3 Correct 603 ms 59812 KB Correct.
4 Correct 484 ms 15464 KB Correct.
5 Correct 881 ms 59572 KB Correct.
6 Correct 403 ms 29456 KB Correct.
7 Correct 470 ms 16488 KB Correct.
8 Correct 484 ms 4416 KB Correct.
9 Correct 223 ms 2368 KB Correct.
10 Correct 224 ms 2792 KB Correct.
11 Correct 482 ms 3096 KB Correct.
12 Correct 259 ms 2384 KB Correct.
13 Correct 247 ms 2416 KB Correct.
14 Correct 399 ms 30476 KB Correct.
15 Correct 465 ms 9820 KB Correct.
16 Correct 230 ms 2344 KB Correct.
17 Correct 272 ms 2356 KB Correct.
18 Correct 262 ms 2316 KB Correct.
19 Correct 647 ms 3388 KB Correct.
20 Correct 20 ms 652 KB Correct.
21 Correct 18 ms 1140 KB Correct.
22 Correct 29 ms 3748 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 1996 KB Wrong Answer.
2 Halted 0 ms 0 KB -