oj.uz

Submission #876753

# Submission time Handle Problem Language Result Execution time Memory
876753 2023-11-22T09:26:36 Z vjudge1 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 162928 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
#pragma GCC target("avx2")

#pragma GCC optimize("O3")

#include <x86intrin.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 1;
vector<pair<int, double>> g[N];
double d[N][70];
double solve(int n, int m, int k, int h, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr)
{   
    k = min(k,69);
    for (int i = 0; i < n; i++)
    {
        for(int j = 0;j <= k;j++){
            d[i][j] = 1e15;
        }
        g[i].clear();
    }
    
    for (int i = 0; i < m; i++)
    {
        g[x[i]].push_back({y[i], c[i]});
        g[y[i]].push_back({x[i], c[i]});
    }
    queue<int> q;
    vector<int> can(n,0);
    can[0] = 1;
    q.push(0);
    priority_queue<pair<double,pair<int,int>>> st;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        if(!can[v]) continue;
        if((arr[v] == 0 || v == 0) && can[v]){
            d[v][0] = 0;
            st.push({0,{0,v}});
        }
        for(auto [to,w]:g[v]){
            if(to == h || can[to]) continue;
            q.push(to);
            can[to] = 1;
        }
    }
    
    st.push({0,{0,0}});
    double res = 1e15;
    while(!st.empty()){
        auto [col,v] = (st.top()).second;
        st.pop();
        if(v == h){
            res = min(res,d[v][col]);
            continue;
        }
        for(auto [to,w]:g[v]){
            if(col + 1 <= k && arr[to] == 2 && d[to][col + 1] > (d[v][col] + w) / 2){
                d[to][col + 1] = (d[v][col] + w) / 2;
                st.push({-d[to][col + 1],{col + 1,to}});
            }
            if(d[to][col] > d[v][col] + w){
                d[to][col] = d[v][col] + w;
                st.push({-d[to][col],{col,to}});
            }
        }
    }
    if(res == 1e15) res = -1;
    return res;
}
// int main() {
//   int T;
//   assert(1 == scanf("%d", &T));
//   while (T--){
//     int N,M,K,H;
//     assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
//     std::vector<int> x(M);
//     std::vector<int> y(M);
//     std::vector<int> c(M);
//     std::vector<int> arr(N);
//     for (int i=0;i<N;i++)
//       assert(1 == scanf("%d", &arr[i]));
//     for (int i=0;i<M;i++)
//       assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
//     printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
//   }
// }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4188 KB Correct.
2 Correct 22 ms 4132 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6492 KB Correct.
2 Correct 22 ms 6480 KB Correct.
3 Correct 22 ms 6492 KB Correct.
4 Correct 22 ms 6488 KB Correct.
5 Correct 22 ms 6492 KB Correct.
6 Correct 20 ms 11356 KB Correct.
7 Correct 25 ms 11360 KB Correct.
8 Correct 13 ms 18248 KB Correct.
9 Correct 21 ms 4192 KB Correct.
10 Correct 20 ms 4188 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6380 KB Correct.
2 Correct 24 ms 6236 KB Correct.
3 Correct 22 ms 6492 KB Correct.
4 Correct 22 ms 4164 KB Correct.
5 Correct 22 ms 4184 KB Correct.
6 Correct 7 ms 11100 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 46536 KB Correct.
2 Correct 293 ms 6788 KB Correct.
3 Correct 235 ms 6748 KB Correct.
4 Correct 250 ms 6788 KB Correct.
5 Correct 221 ms 4484 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6492 KB Correct.
2 Correct 21 ms 6492 KB Correct.
3 Correct 20 ms 6492 KB Correct.
4 Correct 21 ms 11612 KB Correct.
5 Correct 17 ms 4184 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6492 KB Correct.
2 Correct 18 ms 6460 KB Correct.
3 Correct 42 ms 54100 KB Correct.
4 Correct 15 ms 9308 KB Correct.
5 Correct 20 ms 4188 KB Correct.
6 Correct 20 ms 6616 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 7364 KB Correct.
2 Correct 40 ms 8088 KB Correct.
3 Correct 600 ms 68040 KB Correct.
4 Correct 469 ms 19888 KB Correct.
5 Correct 1046 ms 65548 KB Correct.
6 Correct 555 ms 50344 KB Correct.
7 Correct 449 ms 21352 KB Correct.
8 Correct 481 ms 6972 KB Correct.
9 Correct 245 ms 7976 KB Correct.
10 Correct 259 ms 7468 KB Correct.
11 Correct 467 ms 6672 KB Correct.
12 Correct 271 ms 7412 KB Correct.
13 Correct 290 ms 7424 KB Correct.
14 Correct 378 ms 37128 KB Correct.
15 Correct 446 ms 14304 KB Correct.
16 Correct 259 ms 7324 KB Correct.
17 Correct 315 ms 7372 KB Correct.
18 Correct 304 ms 7520 KB Correct.
19 Correct 688 ms 7264 KB Correct.
20 Correct 24 ms 4696 KB Correct.
21 Correct 20 ms 6716 KB Correct.
22 Correct 44 ms 8912 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 961 ms 10372 KB Correct.
2 Correct 137 ms 13000 KB Correct.
3 Correct 584 ms 65828 KB Correct.
4 Correct 1016 ms 10952 KB Correct.
5 Execution timed out 3036 ms 162928 KB Time limit exceeded
6 Halted 0 ms 0 KB -