oj.uz

Submission #986698

# Submission time Handle Problem Language Result Execution time Memory
986698 2024-05-21T04:18:27 Z CSQ31 Cyberland (APIO23_cyberland) C++17
97 / 100
 479 ms 58616 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;
 
typedef long double ld;
ld dist[31][111111];
ld pw[31];
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<=30;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]});
    }
 
    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 3672 KB Correct.
2 Correct 30 ms 3928 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4696 KB Correct.
2 Correct 31 ms 4944 KB Correct.
3 Correct 29 ms 4888 KB Correct.
4 Correct 29 ms 4760 KB Correct.
5 Correct 29 ms 4952 KB Correct.
6 Correct 26 ms 9564 KB Correct.
7 Correct 34 ms 9820 KB Correct.
8 Correct 18 ms 14660 KB Correct.
9 Correct 38 ms 4188 KB Correct.
10 Correct 29 ms 4176 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4700 KB Correct.
2 Correct 29 ms 4700 KB Correct.
3 Correct 30 ms 4244 KB Correct.
4 Correct 30 ms 4276 KB Correct.
5 Correct 33 ms 4140 KB Correct.
6 Correct 8 ms 7772 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 36688 KB Correct.
2 Correct 28 ms 4764 KB Correct.
3 Correct 24 ms 4764 KB Correct.
4 Correct 35 ms 4860 KB Correct.
5 Correct 38 ms 4284 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4696 KB Correct.
2 Correct 29 ms 4956 KB Correct.
3 Correct 27 ms 4944 KB Correct.
4 Correct 27 ms 9732 KB Correct.
5 Correct 25 ms 4440 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4688 KB Correct.
2 Correct 25 ms 4696 KB Correct.
3 Correct 55 ms 47188 KB Correct.
4 Correct 27 ms 7920 KB Correct.
5 Correct 28 ms 4180 KB Correct.
6 Correct 27 ms 4700 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 5156 KB Correct.
2 Correct 21 ms 4448 KB Correct.
3 Correct 479 ms 58616 KB Correct.
4 Correct 275 ms 17580 KB Correct.
5 Correct 391 ms 27548 KB Correct.
6 Correct 235 ms 14792 KB Correct.
7 Correct 301 ms 18608 KB Correct.
8 Correct 208 ms 7252 KB Correct.
9 Correct 105 ms 5036 KB Correct.
10 Correct 99 ms 5112 KB Correct.
11 Correct 165 ms 5828 KB Correct.
12 Correct 98 ms 5088 KB Correct.
13 Correct 100 ms 4992 KB Correct.
14 Correct 283 ms 30712 KB Correct.
15 Correct 291 ms 12264 KB Correct.
16 Correct 103 ms 5120 KB Correct.
17 Correct 107 ms 5116 KB Correct.
18 Correct 97 ms 5056 KB Correct.
19 Correct 146 ms 5712 KB Correct.
20 Correct 11 ms 3416 KB Correct.
21 Correct 11 ms 3932 KB Correct.
22 Correct 20 ms 4700 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 6744 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -