oj.uz

Submission #879232

# Submission time Handle Problem Language Result Execution time Memory
879232 2023-11-27T02:11:01 Z dimashhh Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 164616 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx2")
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 18 ms 4440 KB Correct.
2 Correct 18 ms 4444 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7004 KB Correct.
2 Correct 23 ms 7124 KB Correct.
3 Correct 21 ms 7180 KB Correct.
4 Correct 22 ms 7004 KB Correct.
5 Correct 22 ms 7260 KB Correct.
6 Correct 20 ms 12156 KB Correct.
7 Correct 26 ms 12112 KB Correct.
8 Correct 13 ms 18516 KB Correct.
9 Correct 20 ms 4696 KB Correct.
10 Correct 21 ms 4776 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7172 KB Correct.
2 Correct 23 ms 7004 KB Correct.
3 Correct 21 ms 7040 KB Correct.
4 Correct 22 ms 4880 KB Correct.
5 Correct 21 ms 4956 KB Correct.
6 Correct 7 ms 11356 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 46996 KB Correct.
2 Correct 274 ms 7516 KB Correct.
3 Correct 238 ms 7568 KB Correct.
4 Correct 250 ms 7412 KB Correct.
5 Correct 209 ms 4876 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7260 KB Correct.
2 Correct 21 ms 7336 KB Correct.
3 Correct 21 ms 7260 KB Correct.
4 Correct 22 ms 12316 KB Correct.
5 Correct 18 ms 4956 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7256 KB Correct.
2 Correct 22 ms 7516 KB Correct.
3 Correct 40 ms 55380 KB Correct.
4 Correct 14 ms 9944 KB Correct.
5 Correct 19 ms 4872 KB Correct.
6 Correct 20 ms 7296 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 8276 KB Correct.
2 Correct 41 ms 8208 KB Correct.
3 Correct 556 ms 69480 KB Correct.
4 Correct 466 ms 20848 KB Correct.
5 Correct 1024 ms 66412 KB Correct.
6 Correct 524 ms 50128 KB Correct.
7 Correct 449 ms 22620 KB Correct.
8 Correct 469 ms 8268 KB Correct.
9 Correct 247 ms 8420 KB Correct.
10 Correct 250 ms 8240 KB Correct.
11 Correct 470 ms 7976 KB Correct.
12 Correct 261 ms 8300 KB Correct.
13 Correct 281 ms 8144 KB Correct.
14 Correct 374 ms 38260 KB Correct.
15 Correct 450 ms 15692 KB Correct.
16 Correct 253 ms 8312 KB Correct.
17 Correct 305 ms 8068 KB Correct.
18 Correct 302 ms 8208 KB Correct.
19 Correct 698 ms 8588 KB Correct.
20 Correct 21 ms 4440 KB Correct.
21 Correct 21 ms 6948 KB Correct.
22 Correct 40 ms 9168 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 11048 KB Correct.
2 Correct 128 ms 14156 KB Correct.
3 Correct 521 ms 67372 KB Correct.
4 Correct 1010 ms 12464 KB Correct.
5 Execution timed out 3060 ms 164616 KB Time limit exceeded
6 Halted 0 ms 0 KB -