oj.uz

Submission #770179

# Submission time Handle Problem Language Result Execution time Memory
770179 2023-06-30T22:52:34 Z gg123_pe Cyberland (APIO23_cyberland) C++17
5 / 100
 693 ms 40104 KB 
#include <bits/stdc++.h> 
#include "cyberland.h"

using namespace std; 

#define f(i,a,b) for(int i = a; i < b; i++)
typedef pair <double, pair<int, int>> ii; 

const int N = 1e5 + 5; 
const double inf = 2e15; 

int n, k; 
double d[N][71]; 
bool vis[N]; 
vector <pair<int, double>> adj[N], adj_H; 
vector <int> ARR; 

void check(int u){
    vis[u] = 1; 
    for(auto p: adj[u]){
        int v = p.first; 
        if(!vis[v]) check(v); 
    }
}
void clear(){
    adj_H.clear(); ARR.clear();  
    f(i,0,n) adj[i].clear(), vis[i] = 0;
}
void dij(){
    priority_queue <ii, vector <ii>, greater <ii>> q; 
    f(i,1,n) {
        f(j,0,k+1) d[i][j] = inf; 
    }
    f(j,0,k+1){
        d[0][j] = 0; 
        q.push({0, {j, 0}}); 
    }

    while(!q.empty()){
        auto pa = q.top(); q.pop(); 
        double d_u = pa.first; int u = pa.second.second; int c = pa.second.first;  

        if(d[u][c] != d_u) continue; 
        for(auto p: adj[u]){
            int v = p.first; double w = p.second; 
            int new_ = 0; 
            if(ARR[v] != 0) new_ = d[u][c] + w; 

            if(d[v][c] > new_){
                d[v][c] = new_; 
                q.push({d[v][c], {c, v}}); 
            }
            if(ARR[v] == 2 and c+1 <= k){
                double val = (d[u][c] + w) / 2;  
                if(d[v][c+1] > val){
                    d[v][c+1] = val; 
                    q.push({d[v][c+1], {c+1, v}}); 
                }
            }
        }
    }
}
double solve(int Ni, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    n = Ni; 
    ARR = arr; 
    k = min(70, K); 

    f(i,0,M){
        if(x[i] == H or y[i] == H){
            adj_H.push_back({x[i] + y[i] - H, c[i]}); 
        }
        else {
            adj[x[i]].push_back({y[i], c[i]}); 
            adj[y[i]].push_back({x[i], c[i]}); 
        }
    }
    check(0); 
    dij(); 
    
    double ans = inf; 
    for(auto p: adj_H) {
        int v = p.first; double w = p.second; 
        if(vis[v]) f(i,0,k+1) ans = min(ans, d[v][i] + w); 
    }
    clear(); 
    return (ans == inf) ? -1 : ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2772 KB Correct.
2 Correct 26 ms 2760 KB Correct.

Subtask #2
0.0 / 8.0

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

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 274 ms 3532 KB Double -1.11294e+09 violates the range [-1, 1e+18]
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 40104 KB Correct.
2 Incorrect 260 ms 3412 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 3792 KB Double -9.8642e+07 violates the range [-1, 1e+18]
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 3852 KB Double -8.32333e+08 violates the range [-1, 1e+18]
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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