oj.uz

Submission #770182

# Submission time Handle Problem Language Result Execution time Memory
770182 2023-06-30T22:54:21 Z gg123_pe Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 95028 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; 
            double 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 25 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 3632 KB Correct.
2 Correct 224 ms 3600 KB Correct.
3 Correct 210 ms 3592 KB Correct.
4 Correct 219 ms 3596 KB Correct.
5 Correct 220 ms 3752 KB Correct.
6 Correct 199 ms 10484 KB Correct.
7 Correct 266 ms 10396 KB Correct.
8 Correct 114 ms 17348 KB Correct.
9 Correct 169 ms 2784 KB Correct.
10 Correct 166 ms 2808 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 3516 KB Correct.
2 Correct 238 ms 3504 KB Correct.
3 Correct 221 ms 3608 KB Correct.
4 Correct 207 ms 2804 KB Correct.
5 Correct 207 ms 2916 KB Correct.
6 Correct 48 ms 8412 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 40072 KB Correct.
2 Correct 448 ms 3392 KB Correct.
3 Correct 372 ms 3340 KB Correct.
4 Correct 404 ms 3468 KB Correct.
5 Correct 263 ms 2816 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 3844 KB Correct.
2 Correct 121 ms 3708 KB Correct.
3 Correct 131 ms 3672 KB Correct.
4 Correct 134 ms 11016 KB Correct.
5 Correct 96 ms 2820 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 3820 KB Correct.
2 Correct 115 ms 3856 KB Correct.
3 Correct 51 ms 51492 KB Correct.
4 Correct 89 ms 9596 KB Correct.
5 Correct 123 ms 2944 KB Correct.
6 Correct 133 ms 3816 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 3940 KB Correct.
2 Correct 29 ms 4720 KB Correct.
3 Correct 1354 ms 65084 KB Correct.
4 Correct 1038 ms 17160 KB Correct.
5 Correct 635 ms 45736 KB Correct.
6 Correct 259 ms 22588 KB Correct.
7 Correct 1026 ms 18424 KB Correct.
8 Correct 922 ms 5176 KB Correct.
9 Correct 221 ms 3972 KB Correct.
10 Correct 234 ms 4292 KB Correct.
11 Correct 864 ms 3828 KB Correct.
12 Correct 235 ms 3904 KB Correct.
13 Correct 238 ms 4144 KB Correct.
14 Correct 889 ms 33892 KB Correct.
15 Correct 1186 ms 11328 KB Correct.
16 Correct 218 ms 3912 KB Correct.
17 Correct 272 ms 4140 KB Correct.
18 Correct 275 ms 3912 KB Correct.
19 Correct 813 ms 4284 KB Correct.
20 Correct 17 ms 2772 KB Correct.
21 Correct 21 ms 3664 KB Correct.
22 Correct 22 ms 4992 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 5184 KB Correct.
2 Correct 73 ms 5688 KB Correct.
3 Correct 722 ms 68392 KB Correct.
4 Correct 2577 ms 8528 KB Correct.
5 Correct 1806 ms 95028 KB Correct.
6 Correct 706 ms 47252 KB Correct.
7 Execution timed out 3082 ms 31364 KB Time limit exceeded
8 Halted 0 ms 0 KB -