oj.uz

Submission #804554

# Submission time Handle Problem Language Result Execution time Memory
804554 2023-08-03T09:46:33 Z Theo830 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 52376 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][35];
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>());
    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 472 KB Correct.
2 Correct 15 ms 728 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 800 KB Correct.
2 Correct 22 ms 732 KB Correct.
3 Correct 23 ms 852 KB Correct.
4 Correct 22 ms 768 KB Correct.
5 Correct 22 ms 724 KB Correct.
6 Correct 20 ms 4156 KB Correct.
7 Correct 29 ms 3984 KB Correct.
8 Correct 17 ms 7788 KB Correct.
9 Correct 23 ms 396 KB Correct.
10 Correct 19 ms 400 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 760 KB Correct.
2 Correct 27 ms 800 KB Correct.
3 Correct 23 ms 788 KB Correct.
4 Correct 22 ms 412 KB Correct.
5 Correct 24 ms 404 KB Correct.
6 Correct 6 ms 3540 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 24868 KB Correct.
2 Correct 257 ms 1664 KB Correct.
3 Correct 231 ms 1528 KB Correct.
4 Correct 238 ms 1512 KB Correct.
5 Correct 195 ms 1124 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 724 KB Correct.
2 Correct 21 ms 724 KB Correct.
3 Correct 20 ms 724 KB Correct.
4 Correct 22 ms 4284 KB Correct.
5 Correct 18 ms 404 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 768 KB Correct.
2 Correct 18 ms 728 KB Correct.
3 Correct 43 ms 29300 KB Correct.
4 Correct 14 ms 3412 KB Correct.
5 Correct 19 ms 404 KB Correct.
6 Correct 20 ms 840 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 1280 KB Correct.
2 Correct 36 ms 2308 KB Correct.
3 Correct 637 ms 41024 KB Correct.
4 Correct 508 ms 10916 KB Correct.
5 Correct 953 ms 52376 KB Correct.
6 Correct 441 ms 27088 KB Correct.
7 Correct 497 ms 11596 KB Correct.
8 Correct 503 ms 3448 KB Correct.
9 Correct 225 ms 1948 KB Correct.
10 Correct 228 ms 2404 KB Correct.
11 Correct 517 ms 2604 KB Correct.
12 Correct 239 ms 1988 KB Correct.
13 Correct 249 ms 1960 KB Correct.
14 Correct 388 ms 21184 KB Correct.
15 Correct 468 ms 7160 KB Correct.
16 Correct 230 ms 1924 KB Correct.
17 Correct 289 ms 1916 KB Correct.
18 Correct 273 ms 1828 KB Correct.
19 Correct 655 ms 2928 KB Correct.
20 Correct 18 ms 636 KB Correct.
21 Correct 18 ms 980 KB Correct.
22 Correct 29 ms 3512 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 9708 KB Time limit exceeded
2 Halted 0 ms 0 KB -