oj.uz

Submission #982390

# Submission time Handle Problem Language Result Execution time Memory
982390 2024-05-14T07:58:40 Z Alkaser_ID Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 74300 KB 
#include "cyberland.h"
using namespace std;
#include <bits/stdc++.h>
typedef long double db;
typedef long long ll;

ll n,m,tar,kK=0;
int ab[100005];
db res = -1;
vector<pair<int,db>> adj[100005];
db dis[100005][33];
inline void bfs(int i,int k){
    vector<pair<int,int>> bs;
    for(int j=0;j<adj[i].size();++j){
        if(adj[i][j].first == tar) {
            res = min(res,dis[i][k] + adj[i][j].second);
        }
        else{
            ll nx = adj[i][j].first;db vl = adj[i][j].second,cr = dis[i][k];
            if(ab[nx] == 0 && dis[nx][k] > 0){
                dis[nx][k] = 0;
                bs.push_back({nx,k});
            }
            if(cr + vl < dis[nx][k]) {
                dis[nx][k] = cr + vl;
                bs.push_back({nx,k});
            }
            if(ab[nx] == 2 && k < kK){
                if(((cr + vl) / 2) < dis[nx][k+1]){
                    dis[nx][k+1] = (cr + vl) / 2;
                    bs.push_back({nx,k+1});
                }
            }
        }
    }
    for(int j=0;j<bs.size();++j){
        bfs(bs[j].first,bs[j].second);
    }
}
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) {
    n = N;m = M;
    tar = H; kK = K;
    for(int i=0;i<n;++i) ab[i] = arr[i];
    for(int i=0;i<=n;++i) adj[i].clear();
    res = 1e15;
    for(int i=0;i<m;++i) {
        adj[x[i]].push_back({y[i],c[i]});
        adj[y[i]].push_back({x[i],c[i]});
    }
    for(ll i=0;i<n;++i){
        for(ll j=0;j<=K;++j) dis[i][j] = 1e15;
    }
    dis[0][0] = 0;
    bfs(0,0);
    if(res == 1e15) return -1;
    return res;
}

/*
1
3 2 30
2
1 2 1
1 2 12
2 0 4

1
4 4 30
3
1 0 2 1
0 1 5
0 2 4
1 3 2
2 3 4

*/

Compilation message

cyberland.cpp: In function 'void bfs(int, int)':
cyberland.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int j=0;j<adj[i].size();++j){
      |                 ~^~~~~~~~~~~~~~
cyberland.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int j=0;j<bs.size();++j){
      |                 ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3416 KB Correct.
2 Correct 19 ms 3420 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6232 KB Correct.
2 Correct 27 ms 6488 KB Correct.
3 Correct 26 ms 6236 KB Correct.
4 Correct 29 ms 6488 KB Correct.
5 Correct 26 ms 6492 KB Correct.
6 Correct 23 ms 11612 KB Correct.
7 Correct 29 ms 11868 KB Correct.
8 Correct 14 ms 16220 KB Correct.
9 Correct 26 ms 3932 KB Correct.
10 Correct 25 ms 3920 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6228 KB Correct.
2 Correct 27 ms 6228 KB Correct.
3 Correct 26 ms 6232 KB Correct.
4 Correct 27 ms 3980 KB Correct.
5 Correct 27 ms 3980 KB Correct.
6 Correct 7 ms 8280 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 44884 KB Correct.
2 Correct 346 ms 6480 KB Correct.
3 Correct 277 ms 6480 KB Correct.
4 Correct 293 ms 6480 KB Correct.
5 Correct 266 ms 3920 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 6480 KB Correct.
2 Correct 102 ms 6736 KB Correct.
3 Correct 113 ms 6640 KB Correct.
4 Correct 780 ms 12920 KB Correct.
5 Correct 31 ms 3856 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6664 KB Correct.
2 Correct 25 ms 6520 KB Correct.
3 Correct 52 ms 53596 KB Correct.
4 Correct 20 ms 9616 KB Correct.
5 Correct 28 ms 4016 KB Correct.
6 Correct 27 ms 6492 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 6568 KB Correct.
2 Correct 81 ms 5724 KB Correct.
3 Correct 2362 ms 74300 KB Correct.
4 Correct 1268 ms 21792 KB Correct.
5 Correct 1724 ms 36076 KB Correct.
6 Correct 1085 ms 20956 KB Correct.
7 Correct 1382 ms 21820 KB Correct.
8 Correct 999 ms 8528 KB Correct.
9 Correct 432 ms 6588 KB Correct.
10 Correct 416 ms 6776 KB Correct.
11 Correct 977 ms 7576 KB Correct.
12 Correct 432 ms 6740 KB Correct.
13 Correct 483 ms 6752 KB Correct.
14 Correct 2700 ms 42792 KB Correct.
15 Correct 1458 ms 16124 KB Correct.
16 Correct 434 ms 6740 KB Correct.
17 Correct 477 ms 6704 KB Correct.
18 Correct 524 ms 6776 KB Correct.
19 Correct 1020 ms 7512 KB Correct.
20 Correct 33 ms 3164 KB Correct.
21 Correct 29 ms 5460 KB Correct.
22 Correct 124 ms 6492 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 16996 KB Time limit exceeded
2 Halted 0 ms 0 KB -