oj.uz

Submission #773293

# Submission time Handle Problem Language Result Execution time Memory
773293 2023-07-04T19:36:43 Z AmirElarbi Cyberland (APIO23_cyberland) C++17
97 / 100
 1141 ms 407136 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 = 120+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 18 ms 5076 KB Correct.
2 Correct 19 ms 5076 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6052 KB Correct.
2 Correct 23 ms 6116 KB Correct.
3 Correct 22 ms 6140 KB Correct.
4 Correct 25 ms 6120 KB Correct.
5 Correct 23 ms 6100 KB Correct.
6 Correct 24 ms 15352 KB Correct.
7 Correct 29 ms 15100 KB Correct.
8 Correct 20 ms 25560 KB Correct.
9 Correct 21 ms 5112 KB Correct.
10 Correct 24 ms 5156 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6100 KB Correct.
2 Correct 27 ms 6100 KB Correct.
3 Correct 22 ms 6100 KB Correct.
4 Correct 24 ms 5176 KB Correct.
5 Correct 23 ms 5156 KB Correct.
6 Correct 10 ms 13652 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 72268 KB Correct.
2 Correct 294 ms 6676 KB Correct.
3 Correct 277 ms 6680 KB Correct.
4 Correct 272 ms 6672 KB Correct.
5 Correct 239 ms 5232 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6108 KB Correct.
2 Correct 22 ms 6180 KB Correct.
3 Correct 22 ms 6148 KB Correct.
4 Correct 25 ms 15412 KB Correct.
5 Correct 18 ms 5168 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6116 KB Correct.
2 Correct 21 ms 6200 KB Correct.
3 Correct 63 ms 84176 KB Correct.
4 Correct 18 ms 12628 KB Correct.
5 Correct 21 ms 5148 KB Correct.
6 Correct 21 ms 6152 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 7508 KB Correct.
2 Correct 43 ms 9356 KB Correct.
3 Correct 644 ms 107872 KB Correct.
4 Correct 528 ms 28820 KB Correct.
5 Correct 1141 ms 94216 KB Correct.
6 Correct 537 ms 68504 KB Correct.
7 Correct 494 ms 31064 KB Correct.
8 Correct 512 ms 9076 KB Correct.
9 Correct 256 ms 8288 KB Correct.
10 Correct 264 ms 7608 KB Correct.
11 Correct 503 ms 6724 KB Correct.
12 Correct 273 ms 7592 KB Correct.
13 Correct 291 ms 7604 KB Correct.
14 Correct 437 ms 56056 KB Correct.
15 Correct 485 ms 19180 KB Correct.
16 Correct 268 ms 7532 KB Correct.
17 Correct 316 ms 7476 KB Correct.
18 Correct 313 ms 7412 KB Correct.
19 Correct 740 ms 7380 KB Correct.
20 Correct 27 ms 5632 KB Correct.
21 Correct 23 ms 6712 KB Correct.
22 Correct 37 ms 9572 KB Correct.

Subtask #8
0.0 / 3.0

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