oj.uz

Submission #1008160

# Submission time Handle Problem Language Result Execution time Memory
1008160 2024-06-26T08:04:19 Z imarn Cyberland (APIO23_cyberland) C++17
97 / 100
 797 ms 68272 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[66][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 24 ms 27736 KB Correct.
2 Correct 28 ms 27740 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27996 KB Correct.
2 Correct 20 ms 27996 KB Correct.
3 Correct 17 ms 27992 KB Correct.
4 Correct 20 ms 27992 KB Correct.
5 Correct 17 ms 27884 KB Correct.
6 Correct 17 ms 28828 KB Correct.
7 Correct 26 ms 28592 KB Correct.
8 Correct 13 ms 29528 KB Correct.
9 Correct 18 ms 27740 KB Correct.
10 Correct 22 ms 27740 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27992 KB Correct.
2 Correct 19 ms 27996 KB Correct.
3 Correct 23 ms 27996 KB Correct.
4 Correct 20 ms 27740 KB Correct.
5 Correct 20 ms 27736 KB Correct.
6 Correct 7 ms 28700 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 38564 KB Correct.
2 Correct 244 ms 28292 KB Correct.
3 Correct 228 ms 28260 KB Correct.
4 Correct 237 ms 28320 KB Correct.
5 Correct 199 ms 27736 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28000 KB Correct.
2 Correct 19 ms 28084 KB Correct.
3 Correct 18 ms 28008 KB Correct.
4 Correct 19 ms 29112 KB Correct.
5 Correct 17 ms 27740 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28028 KB Correct.
2 Correct 15 ms 28004 KB Correct.
3 Correct 33 ms 34256 KB Correct.
4 Correct 13 ms 29020 KB Correct.
5 Correct 19 ms 27880 KB Correct.
6 Correct 22 ms 27996 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 28784 KB Correct.
2 Correct 38 ms 29816 KB Correct.
3 Correct 481 ms 27764 KB Correct.
4 Correct 451 ms 26684 KB Correct.
5 Correct 797 ms 68264 KB Correct.
6 Correct 411 ms 68272 KB Correct.
7 Correct 405 ms 28080 KB Correct.
8 Correct 429 ms 28440 KB Correct.
9 Correct 229 ms 29508 KB Correct.
10 Correct 229 ms 29012 KB Correct.
11 Correct 445 ms 28256 KB Correct.
12 Correct 233 ms 28920 KB Correct.
13 Correct 270 ms 28940 KB Correct.
14 Correct 385 ms 31520 KB Correct.
15 Correct 453 ms 29608 KB Correct.
16 Correct 256 ms 28824 KB Correct.
17 Correct 322 ms 26840 KB Correct.
18 Correct 299 ms 28960 KB Correct.
19 Correct 703 ms 28800 KB Correct.
20 Correct 23 ms 28252 KB Correct.
21 Correct 22 ms 28224 KB Correct.
22 Correct 38 ms 28452 KB Correct.

Subtask #8
0.0 / 3.0

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