oj.uz

Submission #773290

# Submission time Handle Problem Language Result Execution time Memory
773290 2023-07-04T19:34:21 Z AmirElarbi Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 70792 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 = 30+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 <= k; ++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 < k && 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 <= k; ++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 23 ms 5076 KB Correct.
2 Correct 19 ms 5432 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5416 KB Correct.
2 Correct 26 ms 5336 KB Correct.
3 Correct 23 ms 5420 KB Correct.
4 Correct 23 ms 5332 KB Correct.
5 Correct 23 ms 5376 KB Correct.
6 Correct 21 ms 8496 KB Correct.
7 Correct 27 ms 8408 KB Correct.
8 Correct 14 ms 11864 KB Correct.
9 Correct 22 ms 5088 KB Correct.
10 Correct 23 ms 5112 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5460 KB Correct.
2 Correct 24 ms 5456 KB Correct.
3 Correct 23 ms 5460 KB Correct.
4 Correct 23 ms 5116 KB Correct.
5 Correct 24 ms 5076 KB Correct.
6 Correct 8 ms 8020 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 31244 KB Correct.
2 Correct 314 ms 6856 KB Correct.
3 Correct 259 ms 6932 KB Correct.
4 Correct 281 ms 6944 KB Correct.
5 Correct 228 ms 6020 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5516 KB Correct.
2 Correct 22 ms 5444 KB Correct.
3 Correct 21 ms 5488 KB Correct.
4 Correct 23 ms 8540 KB Correct.
5 Correct 22 ms 5076 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5508 KB Correct.
2 Correct 19 ms 5460 KB Correct.
3 Correct 41 ms 30944 KB Correct.
4 Correct 15 ms 7764 KB Correct.
5 Correct 21 ms 5088 KB Correct.
6 Correct 21 ms 5460 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 6776 KB Correct.
2 Correct 44 ms 8396 KB Correct.
3 Correct 636 ms 43064 KB Correct.
4 Correct 510 ms 15808 KB Correct.
5 Correct 1133 ms 70792 KB Correct.
6 Correct 516 ms 62724 KB Correct.
7 Correct 488 ms 15636 KB Correct.
8 Correct 532 ms 8300 KB Correct.
9 Correct 255 ms 8204 KB Correct.
10 Correct 257 ms 7712 KB Correct.
11 Correct 513 ms 7668 KB Correct.
12 Correct 279 ms 7540 KB Correct.
13 Correct 295 ms 7668 KB Correct.
14 Correct 403 ms 25572 KB Correct.
15 Correct 485 ms 12504 KB Correct.
16 Correct 261 ms 7680 KB Correct.
17 Correct 318 ms 7696 KB Correct.
18 Correct 319 ms 7744 KB Correct.
19 Correct 744 ms 8636 KB Correct.
20 Correct 23 ms 5672 KB Correct.
21 Correct 23 ms 6096 KB Correct.
22 Correct 37 ms 9032 KB Correct.

Subtask #8
0.0 / 3.0

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