oj.uz

Submission #1008163

# Submission time Handle Problem Language Result Execution time Memory
1008163 2024-06-26T08:04:52 Z imarn Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 193396 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
using namespace std;
const int mxn=1e5+5;
vector<pair<int,double>>g[mxn];
double d[67][mxn]{0};
bool vis[mxn]{0};
void dfs(int u,int n){
    vis[u]=1;
    for(auto v:g[u]){
        if(v.f==n||vis[v.f])continue;
        dfs(v.f,n);
    }
}
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,66);for(int i=0;i<M;i++)g[x[i]].pb({y[i],c[i]}),g[y[i]].pb({x[i],c[i]});dfs(0,H);
    for(int i=0;i<=K;i++)for(int j=0;j<N;j++)d[i][j]=1e17;
    priority_queue<pair<double,pii>,vector<pair<double,pii>>,greater<pair<double,pii>>>q;d[0][0]=0;q.push({0,{0,0}});
    for(int i=1;i<N;i++)if(arr[i]==0&&vis[i])d[0][i]=0,q.push({0,{0,i}});
    while(!q.empty()){
        auto u=q.top();q.pop();
        if(d[u.s.f][u.s.s]<u.f)continue;
        if(u.s.s==H)continue;
        for(auto v:g[u.s.s]){
            if(d[u.s.f][v.f]>u.f+v.s)d[u.s.f][v.f]=u.f+v.s,q.push({u.f+v.s,{u.s.f,v.f}});
            if(arr[v.f]==2&&u.s.f<K){
                double t = (u.f+v.s)/2;
                if(d[u.s.f+1][v.f]>t)d[u.s.f+1][v.f]=t,q.push({t,{u.s.f+1,v.f}});
            }
        }
    }double ans=1e17;
    for(int i=0;i<=K;i++)ans=min(ans,d[i][H]);
    for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis);
    return (ans>=1e17?-1:ans);
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:43:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   43 |     for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis);
      |     ^~~
cyberland.cpp:43:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |     for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis);
      |                                      ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28508 KB Correct.
2 Correct 25 ms 28508 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28568 KB Correct.
2 Correct 20 ms 28764 KB Correct.
3 Correct 18 ms 28764 KB Correct.
4 Correct 21 ms 28760 KB Correct.
5 Correct 19 ms 28764 KB Correct.
6 Correct 18 ms 29432 KB Correct.
7 Correct 21 ms 29532 KB Correct.
8 Correct 13 ms 30192 KB Correct.
9 Correct 19 ms 28644 KB Correct.
10 Correct 18 ms 28508 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28760 KB Correct.
2 Correct 22 ms 28768 KB Correct.
3 Correct 18 ms 28760 KB Correct.
4 Correct 19 ms 28508 KB Correct.
5 Correct 21 ms 28508 KB Correct.
6 Correct 7 ms 29272 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 38392 KB Correct.
2 Correct 275 ms 29256 KB Correct.
3 Correct 213 ms 29096 KB Correct.
4 Correct 236 ms 29020 KB Correct.
5 Correct 192 ms 28508 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28760 KB Correct.
2 Correct 19 ms 28860 KB Correct.
3 Correct 17 ms 28876 KB Correct.
4 Correct 17 ms 30040 KB Correct.
5 Correct 15 ms 28648 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28764 KB Correct.
2 Correct 15 ms 28768 KB Correct.
3 Correct 30 ms 35152 KB Correct.
4 Correct 14 ms 29784 KB Correct.
5 Correct 19 ms 28508 KB Correct.
6 Correct 18 ms 28760 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 29568 KB Correct.
2 Correct 38 ms 30596 KB Correct.
3 Correct 441 ms 28480 KB Correct.
4 Correct 418 ms 27456 KB Correct.
5 Correct 872 ms 69796 KB Correct.
6 Correct 383 ms 68524 KB Correct.
7 Correct 387 ms 28844 KB Correct.
8 Correct 408 ms 29224 KB Correct.
9 Correct 216 ms 30248 KB Correct.
10 Correct 214 ms 29772 KB Correct.
11 Correct 416 ms 29064 KB Correct.
12 Correct 216 ms 29684 KB Correct.
13 Correct 257 ms 29812 KB Correct.
14 Correct 319 ms 32292 KB Correct.
15 Correct 393 ms 30492 KB Correct.
16 Correct 222 ms 29688 KB Correct.
17 Correct 286 ms 29664 KB Correct.
18 Correct 269 ms 29660 KB Correct.
19 Correct 624 ms 29608 KB Correct.
20 Correct 20 ms 29020 KB Correct.
21 Correct 25 ms 29176 KB Correct.
22 Correct 34 ms 31224 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 59052 KB Correct.
2 Correct 122 ms 61988 KB Correct.
3 Correct 406 ms 65108 KB Correct.
4 Correct 947 ms 57796 KB Correct.
5 Execution timed out 3092 ms 193396 KB Time limit exceeded
6 Halted 0 ms 0 KB -