oj.uz

Submission #986700

# Submission time Handle Problem Language Result Execution time Memory
986700 2024-05-21T04:21:32 Z CSQ31 Cyberland (APIO23_cyberland) C++17
97 / 100
 410 ms 56208 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;
 
typedef long double ld;
ld dist[61][111111];
ld pw[61];
struct node{
    int v,k;
    ld dist = 0;
    node(int _v,int _k,ld _dist = 0){
        v = _v;
        k = _k;
        dist = _dist;
    }
};
 
struct comp
{
    bool operator() (node const &a, node const &b) { return a.dist - b.dist > 1e-10; }
};
vector<pair<int,int>>adj[111111];
double solve(int n, int m,int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
    priority_queue<node,vector<node>,comp>pq;
    for(int j=0;j<n;j++){
        adj[j].clear();
        for(int i=0;i<=30;i++){
            dist[i][j] = 1e15;
        }
    }
    pw[0] = 1;
    for(int i=1;i<=60;i++)pw[i] = pw[i-1]*2;
    for(int i=0;i<m;i++){
        adj[x[i]].push_back({y[i],c[i]});
        adj[y[i]].push_back({x[i],c[i]});
    }
    K = min(K,60);
    dist[0][H] = 0;
    pq.push(node(H,0));
    while(!pq.empty()){
        node tmp = pq.top();
        int v = tmp.v;
        int k = tmp.k;
        //cout<<v<<" "<<k<<" "<<tmp.dist<<" "<<dist[k][v]<<'\n';
        pq.pop();
        if(abs(tmp.dist - dist[k][v]) > 1e-10)continue;
        if(arr[v] == 0)continue;
 
        for(pair<int,int>x : adj[v]){
            int u = x.first;
          if(u == H)continue;
            ld w = x.second/pw[k];
            if(dist[k][u] - dist[k][v] - w > 1e-10){
                dist[k][u] = dist[k][v] + w;
                pq.push(node(u,k,dist[k][u]));
            }
            if(arr[u] == 2 && k+1 <= K){
                if(dist[k+1][u] - dist[k][v] - w > 1e-10){
                    dist[k+1][u] = dist[k][v] + w;
                    pq.push(node(u,k+1,dist[k+1][u]));
                }
 
            }
        }
    }
    ld ans = 1e18;
    for(int i=0;i<=K;i++)ans = min(ans,dist[i][0]);
    queue<int>q;
    vector<int>vis(n,0);
    q.push(0);
    vis[0] = 1;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        if(arr[v] == 0){
            for(int i=0;i<=K;i++)ans = min(ans,dist[i][v]);   
        }
      if(v==H)continue;
        for(pair<int,int>x:adj[v]){
            int u = x.first;
            if(!vis[u]){
                q.push(u);
                vis[u] = 1;
            }
        }
    }
    if(!vis[H])return -1;
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3420 KB Correct.
2 Correct 23 ms 3416 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3928 KB Correct.
2 Correct 29 ms 3932 KB Correct.
3 Correct 35 ms 3888 KB Correct.
4 Correct 30 ms 3676 KB Correct.
5 Correct 32 ms 3932 KB Correct.
6 Correct 26 ms 8788 KB Correct.
7 Correct 34 ms 8536 KB Correct.
8 Correct 18 ms 14172 KB Correct.
9 Correct 28 ms 3392 KB Correct.
10 Correct 27 ms 3164 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3676 KB Correct.
2 Correct 28 ms 3676 KB Correct.
3 Correct 31 ms 3920 KB Correct.
4 Correct 30 ms 3164 KB Correct.
5 Correct 29 ms 3164 KB Correct.
6 Correct 8 ms 7512 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 35276 KB Correct.
2 Correct 27 ms 3888 KB Correct.
3 Correct 24 ms 3672 KB Correct.
4 Correct 25 ms 3672 KB Correct.
5 Correct 39 ms 3164 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3928 KB Correct.
2 Correct 28 ms 3944 KB Correct.
3 Correct 29 ms 3932 KB Correct.
4 Correct 27 ms 8712 KB Correct.
5 Correct 25 ms 3376 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3920 KB Correct.
2 Correct 23 ms 3912 KB Correct.
3 Correct 66 ms 45248 KB Correct.
4 Correct 19 ms 7256 KB Correct.
5 Correct 27 ms 3388 KB Correct.
6 Correct 25 ms 3932 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 4104 KB Correct.
2 Correct 23 ms 4188 KB Correct.
3 Correct 410 ms 56208 KB Correct.
4 Correct 271 ms 15440 KB Correct.
5 Correct 373 ms 25548 KB Correct.
6 Correct 222 ms 13256 KB Correct.
7 Correct 290 ms 16624 KB Correct.
8 Correct 194 ms 5204 KB Correct.
9 Correct 96 ms 4104 KB Correct.
10 Correct 89 ms 4120 KB Correct.
11 Correct 169 ms 4180 KB Correct.
12 Correct 97 ms 3944 KB Correct.
13 Correct 99 ms 4052 KB Correct.
14 Correct 277 ms 29064 KB Correct.
15 Correct 279 ms 10224 KB Correct.
16 Correct 102 ms 4080 KB Correct.
17 Correct 107 ms 4184 KB Correct.
18 Correct 94 ms 4024 KB Correct.
19 Correct 148 ms 3892 KB Correct.
20 Correct 11 ms 3420 KB Correct.
21 Correct 12 ms 3820 KB Correct.
22 Correct 20 ms 4444 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 5144 KB Wrong Answer.
2 Halted 0 ms 0 KB -