oj.uz

Submission #804575

# Submission time Handle Problem Language Result Execution time Memory
804575 2023-08-03T09:55:45 Z Theo830 Cyberland (APIO23_cyberland) C++17
97 / 100
 1027 ms 64836 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][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;
    adj.assign(n+5,vector<ii>());
    k = min(k,67);
    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 17 ms 468 KB Correct.
2 Correct 19 ms 412 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1056 KB Correct.
2 Correct 27 ms 980 KB Correct.
3 Correct 27 ms 1028 KB Correct.
4 Correct 30 ms 980 KB Correct.
5 Correct 24 ms 1048 KB Correct.
6 Correct 28 ms 6708 KB Correct.
7 Correct 35 ms 6572 KB Correct.
8 Correct 16 ms 13140 KB Correct.
9 Correct 26 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 23 ms 1024 KB Correct.
2 Correct 23 ms 968 KB Correct.
3 Correct 21 ms 980 KB Correct.
4 Correct 28 ms 340 KB Correct.
5 Correct 28 ms 420 KB Correct.
6 Correct 7 ms 5716 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 40760 KB Correct.
2 Correct 284 ms 1180 KB Correct.
3 Correct 224 ms 1196 KB Correct.
4 Correct 239 ms 1164 KB Correct.
5 Correct 200 ms 568 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1064 KB Correct.
2 Correct 29 ms 1004 KB Correct.
3 Correct 21 ms 1052 KB Correct.
4 Correct 23 ms 6872 KB Correct.
5 Correct 19 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1108 KB Correct.
2 Correct 18 ms 1000 KB Correct.
3 Correct 65 ms 50048 KB Correct.
4 Correct 19 ms 5304 KB Correct.
5 Correct 24 ms 340 KB Correct.
6 Correct 20 ms 1108 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 1420 KB Correct.
2 Correct 39 ms 2616 KB Correct.
3 Correct 684 ms 64836 KB Correct.
4 Correct 525 ms 14960 KB Correct.
5 Correct 1027 ms 60588 KB Correct.
6 Correct 494 ms 28724 KB Correct.
7 Correct 505 ms 16340 KB Correct.
8 Correct 503 ms 2784 KB Correct.
9 Correct 242 ms 1488 KB Correct.
10 Correct 261 ms 2176 KB Correct.
11 Correct 576 ms 1420 KB Correct.
12 Correct 245 ms 1496 KB Correct.
13 Correct 248 ms 1516 KB Correct.
14 Correct 468 ms 31888 KB Correct.
15 Correct 490 ms 8792 KB Correct.
16 Correct 244 ms 1464 KB Correct.
17 Correct 287 ms 1472 KB Correct.
18 Correct 266 ms 1568 KB Correct.
19 Correct 677 ms 1600 KB Correct.
20 Correct 20 ms 584 KB Correct.
21 Correct 18 ms 1144 KB Correct.
22 Correct 33 ms 3656 KB Correct.

Subtask #8
0.0 / 3.0

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