oj.uz

Submission #1008170

# Submission time Handle Problem Language Result Execution time Memory
1008170 2024-06-26T08:07:05 Z imarn Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 128484 KB 
#include<bits/stdc++.h>
#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;arr[0]=0;
    for(int i=0;i<N;i++)if(arr[i]==0&&vis[i])for(int j=0;j<=K;j++)d[0][i]=0,q.push({0,{j,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:41:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   41 |     for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis);
      |     ^~~
cyberland.cpp:41:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   41 |     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 64 ms 28736 KB Correct.
2 Correct 54 ms 28508 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 28956 KB Correct.
2 Correct 206 ms 28948 KB Correct.
3 Correct 206 ms 28948 KB Correct.
4 Correct 215 ms 28940 KB Correct.
5 Correct 219 ms 28960 KB Correct.
6 Correct 204 ms 30976 KB Correct.
7 Correct 273 ms 30900 KB Correct.
8 Correct 112 ms 32200 KB Correct.
9 Correct 156 ms 28648 KB Correct.
10 Correct 173 ms 28504 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 29540 KB Correct.
2 Correct 395 ms 29572 KB Correct.
3 Correct 346 ms 29652 KB Correct.
4 Correct 310 ms 28756 KB Correct.
5 Correct 297 ms 28736 KB Correct.
6 Correct 93 ms 34768 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 38852 KB Correct.
2 Correct 263 ms 29464 KB Correct.
3 Correct 227 ms 29156 KB Correct.
4 Correct 233 ms 29344 KB Correct.
5 Correct 224 ms 28752 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 29032 KB Correct.
2 Correct 114 ms 29068 KB Correct.
3 Correct 124 ms 29344 KB Correct.
4 Correct 131 ms 31440 KB Correct.
5 Correct 91 ms 28684 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 29688 KB Correct.
2 Correct 168 ms 29608 KB Correct.
3 Correct 34 ms 35160 KB Correct.
4 Correct 145 ms 37068 KB Correct.
5 Correct 184 ms 28736 KB Correct.
6 Correct 206 ms 29620 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 29624 KB Correct.
2 Correct 41 ms 29908 KB Correct.
3 Correct 469 ms 28656 KB Correct.
4 Correct 484 ms 27544 KB Correct.
5 Correct 788 ms 69036 KB Correct.
6 Correct 316 ms 52668 KB Correct.
7 Correct 453 ms 28736 KB Correct.
8 Correct 499 ms 29224 KB Correct.
9 Correct 226 ms 29652 KB Correct.
10 Correct 236 ms 29600 KB Correct.
11 Correct 476 ms 29244 KB Correct.
12 Correct 256 ms 29636 KB Correct.
13 Correct 256 ms 29676 KB Correct.
14 Correct 368 ms 32364 KB Correct.
15 Correct 465 ms 30524 KB Correct.
16 Correct 232 ms 29592 KB Correct.
17 Correct 294 ms 29640 KB Correct.
18 Correct 289 ms 29636 KB Correct.
19 Correct 725 ms 29676 KB Correct.
20 Correct 24 ms 28724 KB Correct.
21 Correct 20 ms 29072 KB Correct.
22 Correct 30 ms 31192 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 57232 KB Correct.
2 Correct 99 ms 58812 KB Correct.
3 Correct 550 ms 65088 KB Correct.
4 Correct 965 ms 57612 KB Correct.
5 Correct 2451 ms 128484 KB Correct.
6 Correct 750 ms 95920 KB Correct.
7 Correct 824 ms 73908 KB Correct.
8 Correct 1137 ms 58280 KB Correct.
9 Correct 588 ms 59024 KB Correct.
10 Correct 551 ms 59412 KB Correct.
11 Execution timed out 3094 ms 56468 KB Time limit exceeded
12 Halted 0 ms 0 KB -