oj.uz

Submission #986704

# Submission time Handle Problem Language Result Execution time Memory
986704 2024-05-21T04:25:05 Z CSQ31 Cyberland (APIO23_cyberland) C++17
97 / 100
 609 ms 113912 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;
 
typedef long double ld;
ld dist[65][111111];
ld pw[65];
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<=64;i++){
            dist[i][j] = 1e15;
        }
    }
    pw[0] = 1;
    for(int i=1;i<=64;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,64);
    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 27 ms 3928 KB Correct.
2 Correct 27 ms 3928 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5460 KB Correct.
2 Correct 44 ms 5712 KB Correct.
3 Correct 37 ms 5680 KB Correct.
4 Correct 40 ms 5476 KB Correct.
5 Correct 38 ms 5712 KB Correct.
6 Correct 36 ms 14932 KB Correct.
7 Correct 48 ms 15184 KB Correct.
8 Correct 25 ms 25180 KB Correct.
9 Correct 35 ms 4444 KB Correct.
10 Correct 35 ms 4444 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5456 KB Correct.
2 Correct 40 ms 5424 KB Correct.
3 Correct 36 ms 4816 KB Correct.
4 Correct 41 ms 6088 KB Correct.
5 Correct 38 ms 8256 KB Correct.
6 Correct 11 ms 12376 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 69456 KB Correct.
2 Correct 40 ms 9296 KB Correct.
3 Correct 32 ms 9048 KB Correct.
4 Correct 33 ms 9276 KB Correct.
5 Correct 44 ms 8276 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5568 KB Correct.
2 Correct 36 ms 9300 KB Correct.
3 Correct 34 ms 9308 KB Correct.
4 Correct 37 ms 18468 KB Correct.
5 Correct 32 ms 8024 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5692 KB Correct.
2 Correct 30 ms 9304 KB Correct.
3 Correct 95 ms 88656 KB Correct.
4 Correct 27 ms 14928 KB Correct.
5 Correct 34 ms 8272 KB Correct.
6 Correct 32 ms 5704 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 9496 KB Correct.
2 Correct 22 ms 9048 KB Correct.
3 Correct 531 ms 109940 KB Correct.
4 Correct 287 ms 31856 KB Correct.
5 Correct 413 ms 48588 KB Correct.
6 Correct 224 ms 23752 KB Correct.
7 Correct 309 ms 34040 KB Correct.
8 Correct 213 ms 12628 KB Correct.
9 Correct 109 ms 9428 KB Correct.
10 Correct 95 ms 9484 KB Correct.
11 Correct 179 ms 6736 KB Correct.
12 Correct 105 ms 9460 KB Correct.
13 Correct 114 ms 9512 KB Correct.
14 Correct 307 ms 55364 KB Correct.
15 Correct 287 ms 22088 KB Correct.
16 Correct 113 ms 9508 KB Correct.
17 Correct 114 ms 9556 KB Correct.
18 Correct 104 ms 9460 KB Correct.
19 Correct 163 ms 10000 KB Correct.
20 Correct 11 ms 7256 KB Correct.
21 Correct 12 ms 8284 KB Correct.
22 Correct 20 ms 9048 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 9780 KB Correct.
2 Correct 40 ms 9308 KB Correct.
3 Incorrect 609 ms 113912 KB Wrong Answer.
4 Halted 0 ms 0 KB -