oj.uz

Submission #770177

# Submission time Handle Problem Language Result Execution time Memory
770177 2023-06-30T22:40:58 Z gg123_pe Cyberland (APIO23_cyberland) C++17
97 / 100
 661 ms 68316 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,0,n) {
        f(j,0,k+1) d[i][j] = inf; 
        if((ARR[i] == 0 or i == 0) and vis[i]){
            f(j,0,k+1) {
                d[i][j] = 0; 
                q.push({0, {j, i}}); 
            }
        }
    }

    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; 
            if(d[v][c] > d[u][c] + w){
                d[v][c] = d[u][c] + w; 
                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(60, 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 29 ms 2772 KB Correct.
2 Correct 26 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 3604 KB Correct.
2 Correct 219 ms 3616 KB Correct.
3 Correct 207 ms 3560 KB Correct.
4 Correct 217 ms 3616 KB Correct.
5 Correct 215 ms 3596 KB Correct.
6 Correct 206 ms 10564 KB Correct.
7 Correct 262 ms 10432 KB Correct.
8 Correct 114 ms 17344 KB Correct.
9 Correct 172 ms 2808 KB Correct.
10 Correct 171 ms 2796 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 3860 KB Correct.
2 Correct 258 ms 3824 KB Correct.
3 Correct 238 ms 3900 KB Correct.
4 Correct 216 ms 2824 KB Correct.
5 Correct 202 ms 2828 KB Correct.
6 Correct 54 ms 9924 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 42984 KB Correct.
2 Correct 227 ms 3740 KB Correct.
3 Correct 195 ms 3716 KB Correct.
4 Correct 211 ms 3764 KB Correct.
5 Correct 177 ms 2772 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 3648 KB Correct.
2 Correct 120 ms 3716 KB Correct.
3 Correct 130 ms 3676 KB Correct.
4 Correct 132 ms 11060 KB Correct.
5 Correct 94 ms 2824 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 3872 KB Correct.
2 Correct 120 ms 3896 KB Correct.
3 Correct 62 ms 51508 KB Correct.
4 Correct 91 ms 10948 KB Correct.
5 Correct 116 ms 2836 KB Correct.
6 Correct 131 ms 3908 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 3920 KB Correct.
2 Correct 31 ms 4696 KB Correct.
3 Correct 541 ms 66116 KB Correct.
4 Correct 490 ms 17788 KB Correct.
5 Correct 661 ms 45772 KB Correct.
6 Correct 247 ms 22596 KB Correct.
7 Correct 475 ms 18968 KB Correct.
8 Correct 499 ms 5184 KB Correct.
9 Correct 173 ms 3916 KB Correct.
10 Correct 177 ms 4036 KB Correct.
11 Correct 473 ms 3804 KB Correct.
12 Correct 198 ms 4020 KB Correct.
13 Correct 194 ms 3980 KB Correct.
14 Correct 375 ms 34284 KB Correct.
15 Correct 450 ms 11480 KB Correct.
16 Correct 176 ms 3932 KB Correct.
17 Correct 216 ms 4040 KB Correct.
18 Correct 208 ms 3872 KB Correct.
19 Correct 548 ms 3864 KB Correct.
20 Correct 15 ms 2772 KB Correct.
21 Correct 15 ms 3572 KB Correct.
22 Correct 21 ms 4944 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 4940 KB Correct.
2 Correct 60 ms 5596 KB Correct.
3 Incorrect 551 ms 68316 KB Wrong Answer.
4 Halted 0 ms 0 KB -