oj.uz

Submission #804570

# Submission time Handle Problem Language Result Execution time Memory
804570 2023-08-03T09:53:02 Z Theo830 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 159068 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;
    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 468 KB Correct.
2 Correct 15 ms 456 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1032 KB Correct.
2 Correct 22 ms 1008 KB Correct.
3 Correct 21 ms 1024 KB Correct.
4 Correct 22 ms 980 KB Correct.
5 Correct 22 ms 1052 KB Correct.
6 Correct 21 ms 6808 KB Correct.
7 Correct 27 ms 6600 KB Correct.
8 Correct 15 ms 13204 KB Correct.
9 Correct 19 ms 432 KB Correct.
10 Correct 19 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 980 KB Correct.
2 Correct 26 ms 1020 KB Correct.
3 Correct 24 ms 1064 KB Correct.
4 Correct 21 ms 428 KB Correct.
5 Correct 21 ms 440 KB Correct.
6 Correct 6 ms 5716 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 40772 KB Correct.
2 Correct 252 ms 1212 KB Correct.
3 Correct 237 ms 1124 KB Correct.
4 Correct 239 ms 1160 KB Correct.
5 Correct 201 ms 448 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1108 KB Correct.
2 Correct 21 ms 1064 KB Correct.
3 Correct 26 ms 1108 KB Correct.
4 Correct 24 ms 6868 KB Correct.
5 Correct 17 ms 432 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1048 KB Correct.
2 Correct 18 ms 1072 KB Correct.
3 Correct 47 ms 50052 KB Correct.
4 Correct 15 ms 5204 KB Correct.
5 Correct 23 ms 340 KB Correct.
6 Correct 20 ms 1112 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 1448 KB Correct.
2 Correct 34 ms 2660 KB Correct.
3 Correct 603 ms 64832 KB Correct.
4 Correct 495 ms 14908 KB Correct.
5 Correct 928 ms 60572 KB Correct.
6 Correct 393 ms 28724 KB Correct.
7 Correct 460 ms 16300 KB Correct.
8 Correct 493 ms 2704 KB Correct.
9 Correct 221 ms 1528 KB Correct.
10 Correct 217 ms 2116 KB Correct.
11 Correct 466 ms 1424 KB Correct.
12 Correct 238 ms 1528 KB Correct.
13 Correct 245 ms 1488 KB Correct.
14 Correct 399 ms 31888 KB Correct.
15 Correct 469 ms 8908 KB Correct.
16 Correct 231 ms 1464 KB Correct.
17 Correct 300 ms 1456 KB Correct.
18 Correct 259 ms 1492 KB Correct.
19 Correct 667 ms 1584 KB Correct.
20 Correct 21 ms 584 KB Correct.
21 Correct 18 ms 1144 KB Correct.
22 Correct 35 ms 3656 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 3020 KB Correct.
2 Correct 101 ms 3592 KB Correct.
3 Correct 656 ms 68436 KB Correct.
4 Correct 1008 ms 5308 KB Correct.
5 Execution timed out 3013 ms 159068 KB Time limit exceeded
6 Halted 0 ms 0 KB -