oj.uz

Submission #773292

# Submission time Handle Problem Language Result Execution time Memory
773292 2023-07-04T19:36:05 Z AmirElarbi Cyberland (APIO23_cyberland) C++17
97 / 100
 1132 ms 216600 KB 
#include <bits/stdc++.h>
#define ve vector
#define vi vector<int>
#define vii vector<ii>
#define ii pair<int,int>
#define fi first
#define se second
#define ll long long
#define INF 1e18+7
#define pb push_back
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
    tree_order_statistics_node_update>;
const int MOD = 1e9+7;
const int nax = 2e5+5;
const int kax = 60+5;
void readio(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}
#include "cyberland.h"
vii adj[nax];
bool vis[nax];
double dist[nax][kax];
void dfs(int u, int nt){
    if(vis[u]) return;
    vis[u] = 1;
    for(auto x : adj[u]){
        if(x.fi == nt) continue;
        dfs(x.fi, nt);
    }
}
double solve(int n, int m, int k, int h, vi x, vi y, vi c, vi arr) {
    for (int i = 0; i < n; ++i)
    {
        adj[i].clear();
        vis[i] = 0;
        for (int j = 0; j <= min(k,kax); ++j)
        {
            dist[i][j] = INF;   
        }
    }
    for (int i = 0; i < m; ++i)
    {
        adj[x[i]].pb({y[i], c[i]});
        adj[y[i]].pb({x[i], c[i]});
    }
    dfs(0,h);
    priority_queue<pair<pair<double,int>,int>, ve<pair<pair<double,int>,int>>, greater<pair<pair<double,int>,int>>> pq;
    for (int i = 0; i < n; ++i)
    {
        if((arr[i] == 0 && vis[i])|| !i){
            dist[i][0] = 0;
            pq.push({{0,0}, i});
        }
    }
    while(!pq.empty()){
        int u = pq.top().se, nb = pq.top().fi.se;
        double cst = pq.top().fi.fi;
        pq.pop();
        if(dist[u][nb] != cst) continue;
        if(u == h) continue;
        for(auto x : adj[u]){
            if(dist[u][nb]+x.se < dist[x.fi][nb]){
                dist[x.fi][nb] = dist[u][nb]+x.se;
                pq.push({{dist[x.fi][nb], nb}, x.fi});
            }
            if(nb < min(k,kax) && arr[x.fi] == 2 && (dist[u][nb]+x.se)*0.5 < dist[x.fi][nb+1]){
                dist[x.fi][nb+1] = (dist[u][nb]+x.se)*0.5;
                pq.push({{dist[x.fi][nb+1], nb+1}, x.fi});
            }
        }
    }
    double ans = INF;
    for (int i = 0; i <= min(k,kax); ++i)
    {
        ans = min(ans, dist[h][i]);
    }
    if(ans == INF) return -1;
    return ans;
}

Compilation message

cyberland.cpp: In function 'void readio()':
cyberland.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cyberland.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5188 KB Correct.
2 Correct 19 ms 5076 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5680 KB Correct.
2 Correct 24 ms 5676 KB Correct.
3 Correct 29 ms 5676 KB Correct.
4 Correct 24 ms 5648 KB Correct.
5 Correct 28 ms 5588 KB Correct.
6 Correct 23 ms 10708 KB Correct.
7 Correct 29 ms 10640 KB Correct.
8 Correct 16 ms 16448 KB Correct.
9 Correct 22 ms 5124 KB Correct.
10 Correct 21 ms 5076 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5672 KB Correct.
2 Correct 25 ms 5684 KB Correct.
3 Correct 24 ms 5736 KB Correct.
4 Correct 28 ms 5092 KB Correct.
5 Correct 29 ms 5128 KB Correct.
6 Correct 9 ms 9872 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 44948 KB Correct.
2 Correct 292 ms 6228 KB Correct.
3 Correct 253 ms 6236 KB Correct.
4 Correct 272 ms 6180 KB Correct.
5 Correct 229 ms 5224 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5692 KB Correct.
2 Correct 22 ms 5632 KB Correct.
3 Correct 22 ms 5672 KB Correct.
4 Correct 24 ms 10844 KB Correct.
5 Correct 21 ms 5116 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5708 KB Correct.
2 Correct 24 ms 5636 KB Correct.
3 Correct 47 ms 48616 KB Correct.
4 Correct 17 ms 9368 KB Correct.
5 Correct 22 ms 5128 KB Correct.
6 Correct 21 ms 5684 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 6996 KB Correct.
2 Correct 42 ms 8600 KB Correct.
3 Correct 607 ms 63296 KB Correct.
4 Correct 506 ms 18704 KB Correct.
5 Correct 1132 ms 77588 KB Correct.
6 Correct 529 ms 63724 KB Correct.
7 Correct 490 ms 19824 KB Correct.
8 Correct 507 ms 7432 KB Correct.
9 Correct 256 ms 7876 KB Correct.
10 Correct 256 ms 7112 KB Correct.
11 Correct 507 ms 6188 KB Correct.
12 Correct 278 ms 7124 KB Correct.
13 Correct 291 ms 7028 KB Correct.
14 Correct 446 ms 34292 KB Correct.
15 Correct 494 ms 13500 KB Correct.
16 Correct 262 ms 6984 KB Correct.
17 Correct 317 ms 6968 KB Correct.
18 Correct 314 ms 6968 KB Correct.
19 Correct 749 ms 6912 KB Correct.
20 Correct 25 ms 5588 KB Correct.
21 Correct 22 ms 6240 KB Correct.
22 Correct 38 ms 9064 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 216600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -