oj.uz

Submission #876743

# Submission time Handle Problem Language Result Execution time Memory
876743 2023-11-22T09:21:55 Z vjudge1 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 163012 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);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto [to,w]:g[v]){
            if(to == h || can[to]) continue;
            q.push(to);
            can[to] = 1;
        }
    }
    priority_queue<pair<double,pair<int,int>>> st;
    st.push({0,{0,0}});
    for (int j = 0; j < n; j++)
    {
        if ((!arr[j] && can[j]) || !j)
        {
            st.push({0,{0,j}});
            d[j][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 17 ms 4188 KB Correct.
2 Correct 17 ms 4196 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6492 KB Correct.
2 Correct 22 ms 6440 KB Correct.
3 Correct 21 ms 6492 KB Correct.
4 Correct 22 ms 6236 KB Correct.
5 Correct 22 ms 6492 KB Correct.
6 Correct 20 ms 11352 KB Correct.
7 Correct 25 ms 11352 KB Correct.
8 Correct 13 ms 18264 KB Correct.
9 Correct 20 ms 4188 KB Correct.
10 Correct 20 ms 4188 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6232 KB Correct.
2 Correct 24 ms 6236 KB Correct.
3 Correct 21 ms 6468 KB Correct.
4 Correct 21 ms 4188 KB Correct.
5 Correct 21 ms 4188 KB Correct.
6 Correct 6 ms 11100 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 47044 KB Correct.
2 Correct 276 ms 6788 KB Correct.
3 Correct 235 ms 6804 KB Correct.
4 Correct 248 ms 6772 KB Correct.
5 Correct 213 ms 4244 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6528 KB Correct.
2 Correct 20 ms 6492 KB Correct.
3 Correct 20 ms 6492 KB Correct.
4 Correct 22 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 20 ms 6492 KB Correct.
2 Correct 18 ms 6492 KB Correct.
3 Correct 39 ms 54100 KB Correct.
4 Correct 15 ms 9308 KB Correct.
5 Correct 20 ms 4184 KB Correct.
6 Correct 19 ms 6492 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 7308 KB Correct.
2 Correct 43 ms 8596 KB Correct.
3 Correct 550 ms 67944 KB Correct.
4 Correct 471 ms 19500 KB Correct.
5 Correct 1012 ms 64636 KB Correct.
6 Correct 567 ms 50492 KB Correct.
7 Correct 445 ms 21424 KB Correct.
8 Correct 469 ms 7020 KB Correct.
9 Correct 246 ms 7960 KB Correct.
10 Correct 249 ms 7488 KB Correct.
11 Correct 465 ms 6716 KB Correct.
12 Correct 261 ms 7568 KB Correct.
13 Correct 279 ms 7440 KB Correct.
14 Correct 385 ms 36728 KB Correct.
15 Correct 445 ms 14304 KB Correct.
16 Correct 248 ms 7444 KB Correct.
17 Correct 304 ms 7424 KB Correct.
18 Correct 321 ms 7524 KB Correct.
19 Correct 709 ms 7288 KB Correct.
20 Correct 22 ms 4444 KB Correct.
21 Correct 20 ms 6716 KB Correct.
22 Correct 41 ms 8908 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 981 ms 10132 KB Correct.
2 Correct 127 ms 12836 KB Correct.
3 Correct 525 ms 65832 KB Correct.
4 Correct 1010 ms 10932 KB Correct.
5 Execution timed out 3065 ms 163012 KB Time limit exceeded
6 Halted 0 ms 0 KB -