oj.uz

Submission #804568

# Submission time Handle Problem Language Result Execution time Memory
804568 2023-08-03T09:51:46 Z Theo830 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 168744 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][105];
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,80);
    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 15 ms 492 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 1236 KB Correct.
2 Correct 22 ms 1296 KB Correct.
3 Correct 22 ms 1236 KB Correct.
4 Correct 23 ms 1308 KB Correct.
5 Correct 22 ms 1364 KB Correct.
6 Correct 25 ms 9452 KB Correct.
7 Correct 28 ms 9236 KB Correct.
8 Correct 18 ms 18516 KB Correct.
9 Correct 20 ms 468 KB Correct.
10 Correct 19 ms 464 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1224 KB Correct.
2 Correct 29 ms 1324 KB Correct.
3 Correct 22 ms 1344 KB Correct.
4 Correct 21 ms 464 KB Correct.
5 Correct 23 ms 464 KB Correct.
6 Correct 7 ms 7892 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 56744 KB Correct.
2 Correct 269 ms 1488 KB Correct.
3 Correct 222 ms 1464 KB Correct.
4 Correct 235 ms 1436 KB Correct.
5 Correct 194 ms 468 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1344 KB Correct.
2 Correct 32 ms 1324 KB Correct.
3 Correct 21 ms 1332 KB Correct.
4 Correct 23 ms 9556 KB Correct.
5 Correct 18 ms 448 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1364 KB Correct.
2 Correct 18 ms 1352 KB Correct.
3 Correct 71 ms 70816 KB Correct.
4 Correct 16 ms 7116 KB Correct.
5 Correct 20 ms 456 KB Correct.
6 Correct 23 ms 1380 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 1768 KB Correct.
2 Correct 35 ms 3072 KB Correct.
3 Correct 684 ms 90864 KB Correct.
4 Correct 513 ms 20848 KB Correct.
5 Correct 949 ms 70292 KB Correct.
6 Correct 398 ms 31472 KB Correct.
7 Correct 481 ms 22896 KB Correct.
8 Correct 478 ms 3620 KB Correct.
9 Correct 219 ms 1736 KB Correct.
10 Correct 221 ms 2376 KB Correct.
11 Correct 482 ms 1688 KB Correct.
12 Correct 253 ms 1788 KB Correct.
13 Correct 249 ms 1716 KB Correct.
14 Correct 398 ms 44508 KB Correct.
15 Correct 472 ms 12228 KB Correct.
16 Correct 239 ms 1792 KB Correct.
17 Correct 271 ms 1644 KB Correct.
18 Correct 260 ms 1748 KB Correct.
19 Correct 641 ms 1864 KB Correct.
20 Correct 17 ms 596 KB Correct.
21 Correct 19 ms 1384 KB Correct.
22 Correct 29 ms 3912 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 928 ms 3268 KB Correct.
2 Correct 117 ms 4040 KB Correct.
3 Correct 698 ms 95936 KB Correct.
4 Correct 1091 ms 7188 KB Correct.
5 Execution timed out 3087 ms 168744 KB Time limit exceeded
6 Halted 0 ms 0 KB -