oj.uz

Submission #1008138

# Submission time Handle Problem Language Result Execution time Memory
1008138 2024-06-26T07:55:44 Z imarn Cyberland (APIO23_cyberland) C++17
97 / 100
 1809 ms 132008 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,long double>>g[mxn];
long double d[65][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,64);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]=1e16;
    priority_queue<pair<long double,pii>,vector<pair<long double,pii>>,greater<pair<long 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&&d[u.s.f+1][v.f]>(u.f+v.s)/2)d[u.s.f+1][v.f]=(u.f+v.s)/2,q.push({(u.f+v.s)/2,{u.s.f+1,v.f}});
        }
    }long double ans=1e16;
    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>=1e15?-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:40:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   40 |     for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis);
      |     ^~~
cyberland.cpp:40:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |     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 38 ms 49548 KB Correct.
2 Correct 53 ms 51528 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 52280 KB Correct.
2 Correct 35 ms 44296 KB Correct.
3 Correct 38 ms 52412 KB Correct.
4 Correct 35 ms 42216 KB Correct.
5 Correct 35 ms 52564 KB Correct.
6 Correct 36 ms 53600 KB Correct.
7 Correct 58 ms 51972 KB Correct.
8 Correct 21 ms 51028 KB Correct.
9 Correct 46 ms 52032 KB Correct.
10 Correct 33 ms 50000 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 52404 KB Correct.
2 Correct 32 ms 52308 KB Correct.
3 Correct 31 ms 52312 KB Correct.
4 Correct 51 ms 52160 KB Correct.
5 Correct 43 ms 52048 KB Correct.
6 Correct 13 ms 52588 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 70428 KB Correct.
2 Correct 481 ms 53168 KB Correct.
3 Correct 442 ms 53076 KB Correct.
4 Correct 467 ms 53152 KB Correct.
5 Correct 371 ms 52284 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 52560 KB Correct.
2 Correct 33 ms 52568 KB Correct.
3 Correct 41 ms 52540 KB Correct.
4 Correct 35 ms 54736 KB Correct.
5 Correct 33 ms 52056 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 52572 KB Correct.
2 Correct 31 ms 52424 KB Correct.
3 Correct 50 ms 64592 KB Correct.
4 Correct 25 ms 53660 KB Correct.
5 Correct 44 ms 52048 KB Correct.
6 Correct 42 ms 52572 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 54328 KB Correct.
2 Correct 74 ms 55092 KB Correct.
3 Correct 1062 ms 52504 KB Correct.
4 Correct 803 ms 50120 KB Correct.
5 Correct 1809 ms 132008 KB Correct.
6 Correct 761 ms 128392 KB Correct.
7 Correct 763 ms 55200 KB Correct.
8 Correct 725 ms 54280 KB Correct.
9 Correct 459 ms 55176 KB Correct.
10 Correct 394 ms 54500 KB Correct.
11 Correct 827 ms 53816 KB Correct.
12 Correct 452 ms 54380 KB Correct.
13 Correct 477 ms 54564 KB Correct.
14 Correct 599 ms 59284 KB Correct.
15 Correct 752 ms 56900 KB Correct.
16 Correct 408 ms 54396 KB Correct.
17 Correct 556 ms 54388 KB Correct.
18 Correct 518 ms 54296 KB Correct.
19 Correct 1201 ms 55288 KB Correct.
20 Correct 38 ms 51996 KB Correct.
21 Correct 40 ms 52332 KB Correct.
22 Correct 63 ms 58060 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1514 ms 84564 KB Correct.
2 Correct 220 ms 89404 KB Correct.
3 Incorrect 939 ms 120148 KB Wrong Answer.
4 Halted 0 ms 0 KB -