oj.uz

Submission #932219

# Submission time Handle Problem Language Result Execution time Memory
932219 2024-02-23T05:43:03 Z Darren0724 Cyberland (APIO23_cyberland) C++17
100 / 100
 2623 ms 19196 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
//#include "stub.cpp"
using namespace std;
#define all(x) x.begin(),x.end()
const long long INF=1e18;
const double eps=1e-6;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> v, vector<int> c1) {
    k=min(k,80);
    vector<pair<int,long long>> adj[n+1];
    for(int i=0;i<m;i++){
        if(x[i]!=h)adj[x[i]].push_back({y[i],v[i]});
        if(y[i]!=h)adj[y[i]].push_back({x[i],v[i]});
    }
    vector vis(n,(int)0);
    queue<int> q;
    q.push(0);
    vis[0]=1;
    while(q.size()){
        int p=q.front();
        q.pop();
        for(auto [a,b]:adj[p]){
            if(!vis[a]){
                vis[a]=1;
                q.push(a);
            }
        }
    }
    if(!vis[h])return -1;
    vector dis(n,(long double)INF),dis1(n,(long double)INF);
    priority_queue<pair<long double ,int>> pq;
    c1[0]=0;
    for(int i=0;i<n;i++){
        if(c1[i]==0){
            dis[i]=0;
        }
    }
    long double ans=INF;
    
    for(int i=0;i<=k;i++){
        for(int j=0;j<n;j++){
            if(vis[j]){
                pq.push({-dis[j],j});
            }
        }
        while(pq.size()){
            auto [a,b]=pq.top();
            pq.pop();
            a=-a;
            if(a!=dis[b])continue;
            for(auto [c,d]:adj[b]){
                long double cost=a+d;
                
                if(cost<dis[c]){
                    dis[c]=cost;
                    pq.push({-dis[c],c});
                }
                if(c1[c]==2)cost/=2;
                if(cost<dis1[c]){
                    dis1[c]=cost;
                }
            }
        }
        ans=min(ans,dis[h]);
        dis=dis1;
        fill(all(dis1),INF);
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 484 KB Correct.
2 Correct 36 ms 572 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 736 KB Correct.
2 Correct 297 ms 692 KB Correct.
3 Correct 342 ms 780 KB Correct.
4 Correct 277 ms 680 KB Correct.
5 Correct 301 ms 692 KB Correct.
6 Correct 295 ms 2672 KB Correct.
7 Correct 389 ms 2668 KB Correct.
8 Correct 165 ms 4308 KB Correct.
9 Correct 206 ms 688 KB Correct.
10 Correct 175 ms 552 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 640 KB Correct.
2 Correct 291 ms 896 KB Correct.
3 Correct 267 ms 708 KB Correct.
4 Correct 200 ms 548 KB Correct.
5 Correct 190 ms 540 KB Correct.
6 Correct 63 ms 1880 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 8916 KB Correct.
2 Correct 185 ms 604 KB Correct.
3 Correct 179 ms 1104 KB Correct.
4 Correct 176 ms 600 KB Correct.
5 Correct 114 ms 528 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 672 KB Correct.
2 Correct 132 ms 628 KB Correct.
3 Correct 128 ms 604 KB Correct.
4 Correct 169 ms 2024 KB Correct.
5 Correct 79 ms 540 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 656 KB Correct.
2 Correct 100 ms 652 KB Correct.
3 Correct 44 ms 8788 KB Correct.
4 Correct 95 ms 1884 KB Correct.
5 Correct 94 ms 596 KB Correct.
6 Correct 117 ms 644 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 612 KB Correct.
2 Correct 29 ms 604 KB Correct.
3 Correct 1014 ms 19196 KB Correct.
4 Correct 648 ms 4980 KB Correct.
5 Correct 523 ms 10988 KB Correct.
6 Correct 196 ms 7896 KB Correct.
7 Correct 598 ms 5256 KB Correct.
8 Correct 477 ms 1060 KB Correct.
9 Correct 127 ms 672 KB Correct.
10 Correct 113 ms 904 KB Correct.
11 Correct 427 ms 1064 KB Correct.
12 Correct 144 ms 640 KB Correct.
13 Correct 141 ms 600 KB Correct.
14 Correct 485 ms 9116 KB Correct.
15 Correct 541 ms 3200 KB Correct.
16 Correct 127 ms 612 KB Correct.
17 Correct 167 ms 640 KB Correct.
18 Correct 142 ms 600 KB Correct.
19 Correct 427 ms 604 KB Correct.
20 Correct 8 ms 344 KB Correct.
21 Correct 10 ms 348 KB Correct.
22 Correct 16 ms 1116 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 596 KB Correct.
2 Correct 52 ms 604 KB Correct.
3 Correct 2348 ms 18888 KB Correct.
4 Correct 693 ms 3196 KB Correct.
5 Correct 1194 ms 12012 KB Correct.
6 Correct 469 ms 8848 KB Correct.
7 Correct 1024 ms 10332 KB Correct.
8 Correct 684 ms 2112 KB Correct.
9 Correct 272 ms 1364 KB Correct.
10 Correct 245 ms 1332 KB Correct.
11 Correct 361 ms 1340 KB Correct.
12 Correct 318 ms 1456 KB Correct.
13 Correct 316 ms 1704 KB Correct.
14 Correct 2037 ms 11036 KB Correct.
15 Correct 2623 ms 10824 KB Correct.
16 Correct 1083 ms 5568 KB Correct.
17 Correct 747 ms 2524 KB Correct.
18 Correct 293 ms 1436 KB Correct.
19 Correct 372 ms 1364 KB Correct.
20 Correct 311 ms 1444 KB Correct.
21 Correct 1020 ms 1864 KB Correct.
22 Correct 16 ms 568 KB Correct.
23 Correct 21 ms 640 KB Correct.
24 Correct 36 ms 1372 KB Correct.