oj.uz

Submission #876796

# Submission time Handle Problem Language Result Execution time Memory
876796 2023-11-22T10:49:16 Z dimashhh Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 162752 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 19 ms 4188 KB Correct.
2 Correct 17 ms 4188 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 6492 KB Correct.
3 Correct 26 ms 6232 KB Correct.
4 Correct 22 ms 6236 KB Correct.
5 Correct 22 ms 6468 KB Correct.
6 Correct 20 ms 11352 KB Correct.
7 Correct 25 ms 11352 KB Correct.
8 Correct 14 ms 18352 KB Correct.
9 Correct 20 ms 4188 KB Correct.
10 Correct 19 ms 4172 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6236 KB Correct.
2 Correct 23 ms 6236 KB Correct.
3 Correct 21 ms 6492 KB Correct.
4 Correct 21 ms 4184 KB Correct.
5 Correct 21 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 220 ms 46428 KB Correct.
2 Correct 280 ms 6940 KB Correct.
3 Correct 233 ms 6800 KB Correct.
4 Correct 256 ms 6956 KB Correct.
5 Correct 208 ms 4228 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6492 KB Correct.
2 Correct 20 ms 6492 KB Correct.
3 Correct 20 ms 6540 KB Correct.
4 Correct 21 ms 11608 KB Correct.
5 Correct 17 ms 4188 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 6492 KB Correct.
3 Correct 40 ms 54100 KB Correct.
4 Correct 14 ms 9304 KB Correct.
5 Correct 20 ms 4196 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 7368 KB Correct.
2 Correct 41 ms 8076 KB Correct.
3 Correct 576 ms 68024 KB Correct.
4 Correct 465 ms 19504 KB Correct.
5 Correct 1032 ms 65644 KB Correct.
6 Correct 539 ms 50372 KB Correct.
7 Correct 447 ms 21340 KB Correct.
8 Correct 465 ms 6992 KB Correct.
9 Correct 247 ms 7976 KB Correct.
10 Correct 246 ms 7380 KB Correct.
11 Correct 475 ms 6720 KB Correct.
12 Correct 259 ms 7404 KB Correct.
13 Correct 278 ms 7520 KB Correct.
14 Correct 376 ms 37008 KB Correct.
15 Correct 450 ms 14404 KB Correct.
16 Correct 252 ms 7412 KB Correct.
17 Correct 303 ms 7388 KB Correct.
18 Correct 308 ms 7364 KB Correct.
19 Correct 687 ms 7288 KB Correct.
20 Correct 21 ms 4544 KB Correct.
21 Correct 20 ms 6720 KB Correct.
22 Correct 41 ms 9044 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 967 ms 10332 KB Correct.
2 Correct 128 ms 12880 KB Correct.
3 Correct 531 ms 65828 KB Correct.
4 Correct 1010 ms 11244 KB Correct.
5 Execution timed out 3054 ms 162752 KB Time limit exceeded
6 Halted 0 ms 0 KB -