oj.uz

Submission #876756

# Submission time Handle Problem Language Result Execution time Memory
876756 2023-11-22T09:29:14 Z vjudge1 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 164576 KB 
#include <bits/stdc++.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,67);
    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 20 ms 4188 KB Correct.
2 Correct 18 ms 4184 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6232 KB Correct.
2 Correct 22 ms 6444 KB Correct.
3 Correct 32 ms 6488 KB Correct.
4 Correct 21 ms 6484 KB Correct.
5 Correct 21 ms 6488 KB Correct.
6 Correct 20 ms 11352 KB Correct.
7 Correct 25 ms 11356 KB Correct.
8 Correct 13 ms 18268 KB Correct.
9 Correct 20 ms 4180 KB Correct.
10 Correct 19 ms 4016 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6440 KB Correct.
2 Correct 22 ms 6236 KB Correct.
3 Correct 20 ms 6492 KB Correct.
4 Correct 23 ms 4168 KB Correct.
5 Correct 23 ms 4188 KB Correct.
6 Correct 6 ms 11096 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 46280 KB Correct.
2 Correct 265 ms 6784 KB Correct.
3 Correct 239 ms 6788 KB Correct.
4 Correct 246 ms 6732 KB Correct.
5 Correct 207 ms 4228 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6488 KB Correct.
2 Correct 20 ms 6488 KB Correct.
3 Correct 19 ms 6488 KB Correct.
4 Correct 20 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 6576 KB Correct.
2 Correct 17 ms 6584 KB Correct.
3 Correct 40 ms 53928 KB Correct.
4 Correct 15 ms 9448 KB Correct.
5 Correct 19 ms 4184 KB Correct.
6 Correct 19 ms 6572 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 7348 KB Correct.
2 Correct 40 ms 8280 KB Correct.
3 Correct 540 ms 67968 KB Correct.
4 Correct 464 ms 19768 KB Correct.
5 Correct 1020 ms 64820 KB Correct.
6 Correct 516 ms 49904 KB Correct.
7 Correct 447 ms 21336 KB Correct.
8 Correct 464 ms 7272 KB Correct.
9 Correct 241 ms 7976 KB Correct.
10 Correct 247 ms 7672 KB Correct.
11 Correct 459 ms 6784 KB Correct.
12 Correct 259 ms 7552 KB Correct.
13 Correct 275 ms 7432 KB Correct.
14 Correct 362 ms 36668 KB Correct.
15 Correct 441 ms 14404 KB Correct.
16 Correct 246 ms 7412 KB Correct.
17 Correct 299 ms 7368 KB Correct.
18 Correct 307 ms 7336 KB Correct.
19 Correct 690 ms 7432 KB Correct.
20 Correct 21 ms 4508 KB Correct.
21 Correct 20 ms 6720 KB Correct.
22 Correct 42 ms 9124 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 9996 KB Correct.
2 Correct 122 ms 14128 KB Correct.
3 Correct 482 ms 65804 KB Correct.
4 Correct 971 ms 10832 KB Correct.
5 Execution timed out 3051 ms 164576 KB Time limit exceeded
6 Halted 0 ms 0 KB -