oj.uz

Submission #1008149

# Submission time Handle Problem Language Result Execution time Memory
1008149 2024-06-26T07:58:54 Z imarn Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 195996 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[70][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,69);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&&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}});
        }
    }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: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 29 ms 29272 KB Correct.
2 Correct 30 ms 29276 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 29652 KB Correct.
2 Correct 21 ms 29784 KB Correct.
3 Correct 31 ms 29824 KB Correct.
4 Correct 21 ms 29840 KB Correct.
5 Correct 26 ms 29776 KB Correct.
6 Correct 20 ms 30556 KB Correct.
7 Correct 33 ms 30632 KB Correct.
8 Correct 13 ms 31064 KB Correct.
9 Correct 29 ms 29528 KB Correct.
10 Correct 27 ms 29596 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29748 KB Correct.
2 Correct 31 ms 29740 KB Correct.
3 Correct 22 ms 29856 KB Correct.
4 Correct 23 ms 29532 KB Correct.
5 Correct 23 ms 29528 KB Correct.
6 Correct 11 ms 29784 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 39396 KB Correct.
2 Correct 277 ms 30008 KB Correct.
3 Correct 250 ms 30080 KB Correct.
4 Correct 226 ms 30184 KB Correct.
5 Correct 195 ms 29724 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 29784 KB Correct.
2 Correct 21 ms 29840 KB Correct.
3 Correct 33 ms 29744 KB Correct.
4 Correct 22 ms 31068 KB Correct.
5 Correct 30 ms 29528 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 29752 KB Correct.
2 Correct 22 ms 29788 KB Correct.
3 Correct 45 ms 36656 KB Correct.
4 Correct 15 ms 30552 KB Correct.
5 Correct 22 ms 29576 KB Correct.
6 Correct 20 ms 29788 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 30700 KB Correct.
2 Correct 42 ms 30860 KB Correct.
3 Correct 560 ms 30316 KB Correct.
4 Correct 494 ms 28868 KB Correct.
5 Correct 1018 ms 70316 KB Correct.
6 Correct 384 ms 69604 KB Correct.
7 Correct 473 ms 30372 KB Correct.
8 Correct 461 ms 30668 KB Correct.
9 Correct 230 ms 30780 KB Correct.
10 Correct 242 ms 30844 KB Correct.
11 Correct 481 ms 30496 KB Correct.
12 Correct 267 ms 30876 KB Correct.
13 Correct 279 ms 30704 KB Correct.
14 Correct 377 ms 33828 KB Correct.
15 Correct 440 ms 32060 KB Correct.
16 Correct 240 ms 30796 KB Correct.
17 Correct 274 ms 30624 KB Correct.
18 Correct 273 ms 30688 KB Correct.
19 Correct 632 ms 31136 KB Correct.
20 Correct 22 ms 29272 KB Correct.
21 Correct 24 ms 29476 KB Correct.
22 Correct 39 ms 31628 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 62116 KB Correct.
2 Correct 124 ms 64376 KB Correct.
3 Correct 452 ms 69156 KB Correct.
4 Correct 938 ms 61532 KB Correct.
5 Execution timed out 3042 ms 195996 KB Time limit exceeded
6 Halted 0 ms 0 KB -