oj.uz

Submission #804562

# Submission time Handle Problem Language Result Execution time Memory
804562 2023-08-03T09:50:15 Z Theo830 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 170332 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,100);
    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 16 ms 468 KB Correct.
2 Correct 15 ms 444 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1344 KB Correct.
2 Correct 25 ms 1356 KB Correct.
3 Correct 24 ms 1304 KB Correct.
4 Correct 23 ms 1236 KB Correct.
5 Correct 23 ms 1324 KB Correct.
6 Correct 23 ms 9504 KB Correct.
7 Correct 29 ms 9268 KB Correct.
8 Correct 17 ms 18516 KB Correct.
9 Correct 20 ms 468 KB Correct.
10 Correct 19 ms 456 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1296 KB Correct.
2 Correct 22 ms 1236 KB Correct.
3 Correct 21 ms 1364 KB Correct.
4 Correct 21 ms 452 KB Correct.
5 Correct 21 ms 468 KB Correct.
6 Correct 7 ms 7892 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 56780 KB Correct.
2 Correct 257 ms 1488 KB Correct.
3 Correct 220 ms 1364 KB Correct.
4 Correct 236 ms 1356 KB Correct.
5 Correct 192 ms 480 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1348 KB Correct.
2 Correct 22 ms 1324 KB Correct.
3 Correct 21 ms 1364 KB Correct.
4 Correct 23 ms 9548 KB Correct.
5 Correct 28 ms 460 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1344 KB Correct.
2 Correct 19 ms 1308 KB Correct.
3 Correct 50 ms 70808 KB Correct.
4 Correct 15 ms 7124 KB Correct.
5 Correct 20 ms 452 KB Correct.
6 Correct 20 ms 1296 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 1760 KB Correct.
2 Correct 33 ms 3020 KB Correct.
3 Correct 639 ms 90844 KB Correct.
4 Correct 496 ms 20752 KB Correct.
5 Correct 950 ms 70320 KB Correct.
6 Correct 421 ms 31540 KB Correct.
7 Correct 494 ms 22864 KB Correct.
8 Correct 487 ms 3672 KB Correct.
9 Correct 224 ms 1772 KB Correct.
10 Correct 223 ms 2380 KB Correct.
11 Correct 474 ms 1692 KB Correct.
12 Correct 246 ms 1764 KB Correct.
13 Correct 251 ms 1776 KB Correct.
14 Correct 402 ms 44524 KB Correct.
15 Correct 483 ms 12228 KB Correct.
16 Correct 255 ms 1776 KB Correct.
17 Correct 286 ms 1744 KB Correct.
18 Correct 266 ms 1692 KB Correct.
19 Correct 648 ms 1836 KB Correct.
20 Correct 18 ms 616 KB Correct.
21 Correct 21 ms 1432 KB Correct.
22 Correct 30 ms 3912 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1123 ms 5448 KB Correct.
2 Correct 142 ms 6280 KB Correct.
3 Correct 912 ms 98200 KB Correct.
4 Correct 1189 ms 9404 KB Correct.
5 Execution timed out 3031 ms 170332 KB Time limit exceeded
6 Halted 0 ms 0 KB -