oj.uz

Submission #1008174

# Submission time Handle Problem Language Result Execution time Memory
1008174 2024-06-26T08:09:01 Z imarn Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 129444 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;d[0][0]=0;q.push({0,{0,0}});arr[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(!arr[v.f])continue;
            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:42:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   42 |     for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis);
      |     ^~~
cyberland.cpp:42:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   42 |     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 23 ms 28508 KB Correct.
2 Correct 24 ms 28748 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28788 KB Correct.
2 Correct 20 ms 28764 KB Correct.
3 Correct 20 ms 28704 KB Correct.
4 Correct 20 ms 28760 KB Correct.
5 Correct 20 ms 28764 KB Correct.
6 Correct 18 ms 29528 KB Correct.
7 Correct 23 ms 29532 KB Correct.
8 Correct 14 ms 30300 KB Correct.
9 Correct 20 ms 28484 KB Correct.
10 Correct 19 ms 28656 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28764 KB Correct.
2 Correct 21 ms 28760 KB Correct.
3 Correct 20 ms 28708 KB Correct.
4 Correct 22 ms 28488 KB Correct.
5 Correct 21 ms 28504 KB Correct.
6 Correct 7 ms 29432 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 35472 KB Correct.
2 Correct 172 ms 28840 KB Correct.
3 Correct 148 ms 28880 KB Correct.
4 Correct 164 ms 28844 KB Correct.
5 Correct 143 ms 28508 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28764 KB Correct.
2 Correct 19 ms 28812 KB Correct.
3 Correct 27 ms 28764 KB Correct.
4 Correct 20 ms 29840 KB Correct.
5 Correct 17 ms 28504 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29016 KB Correct.
2 Correct 17 ms 28760 KB Correct.
3 Correct 32 ms 35164 KB Correct.
4 Correct 14 ms 29788 KB Correct.
5 Correct 20 ms 28648 KB Correct.
6 Correct 18 ms 28764 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 29264 KB Correct.
2 Correct 27 ms 29604 KB Correct.
3 Correct 477 ms 28536 KB Correct.
4 Correct 441 ms 27356 KB Correct.
5 Correct 600 ms 69644 KB Correct.
6 Correct 304 ms 52404 KB Correct.
7 Correct 404 ms 28660 KB Correct.
8 Correct 427 ms 29200 KB Correct.
9 Correct 160 ms 29668 KB Correct.
10 Correct 164 ms 29616 KB Correct.
11 Correct 401 ms 29064 KB Correct.
12 Correct 169 ms 29876 KB Correct.
13 Correct 179 ms 29584 KB Correct.
14 Correct 331 ms 32392 KB Correct.
15 Correct 414 ms 30404 KB Correct.
16 Correct 161 ms 29580 KB Correct.
17 Correct 191 ms 29372 KB Correct.
18 Correct 186 ms 29528 KB Correct.
19 Correct 417 ms 29188 KB Correct.
20 Correct 15 ms 28764 KB Correct.
21 Correct 18 ms 28984 KB Correct.
22 Correct 26 ms 31192 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 57356 KB Correct.
2 Correct 81 ms 58408 KB Correct.
3 Correct 377 ms 65112 KB Correct.
4 Correct 855 ms 57724 KB Correct.
5 Correct 2203 ms 129444 KB Correct.
6 Correct 1075 ms 128936 KB Correct.
7 Correct 974 ms 73248 KB Correct.
8 Correct 1016 ms 56584 KB Correct.
9 Correct 567 ms 59256 KB Correct.
10 Correct 539 ms 58908 KB Correct.
11 Correct 1755 ms 55532 KB Correct.
12 Correct 580 ms 60452 KB Correct.
13 Correct 610 ms 59396 KB Correct.
14 Execution timed out 3028 ms 129188 KB Time limit exceeded
15 Halted 0 ms 0 KB -