oj.uz

Submission #1008213

# Submission time Handle Problem Language Result Execution time Memory
1008213 2024-06-26T08:27:22 Z imarn Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 105592 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+67]{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);
    }
}
priority_queue<pair<double,pii>,vector<pair<double,pii>>,greater<pair<double,pii>>>q;
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;
    d[0][0]=0;q.push({0,{0,0}});arr[0]=0;double ans=1e17;
    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){ans=min(ans,u.f);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.0;
                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}});
            }
        }
    }for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis);
    return (ans>=1e17?-1:ans);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28504 KB Correct.
2 Correct 23 ms 28504 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28764 KB Correct.
2 Correct 17 ms 28764 KB Correct.
3 Correct 17 ms 28760 KB Correct.
4 Correct 18 ms 28764 KB Correct.
5 Correct 18 ms 28692 KB Correct.
6 Correct 16 ms 29532 KB Correct.
7 Correct 20 ms 29528 KB Correct.
8 Correct 10 ms 30300 KB Correct.
9 Correct 18 ms 28508 KB Correct.
10 Correct 17 ms 28640 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28764 KB Correct.
2 Correct 18 ms 28764 KB Correct.
3 Correct 21 ms 28776 KB Correct.
4 Correct 21 ms 28504 KB Correct.
5 Correct 20 ms 28508 KB Correct.
6 Correct 7 ms 29356 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 35360 KB Correct.
2 Correct 165 ms 28764 KB Correct.
3 Correct 137 ms 28848 KB Correct.
4 Correct 141 ms 28760 KB Correct.
5 Correct 126 ms 28508 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28760 KB Correct.
2 Correct 19 ms 28764 KB Correct.
3 Correct 17 ms 28800 KB Correct.
4 Correct 21 ms 29980 KB Correct.
5 Correct 18 ms 28508 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28848 KB Correct.
2 Correct 15 ms 28760 KB Correct.
3 Correct 29 ms 34992 KB Correct.
4 Correct 12 ms 29532 KB Correct.
5 Correct 17 ms 28508 KB Correct.
6 Correct 17 ms 28760 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 29020 KB Correct.
2 Correct 26 ms 29400 KB Correct.
3 Correct 465 ms 28456 KB Correct.
4 Correct 388 ms 21772 KB Correct.
5 Correct 600 ms 60204 KB Correct.
6 Correct 298 ms 41664 KB Correct.
7 Correct 392 ms 24912 KB Correct.
8 Correct 353 ms 19024 KB Correct.
9 Correct 153 ms 19160 KB Correct.
10 Correct 143 ms 21252 KB Correct.
11 Correct 347 ms 16940 KB Correct.
12 Correct 147 ms 19180 KB Correct.
13 Correct 156 ms 19152 KB Correct.
14 Correct 297 ms 25940 KB Correct.
15 Correct 380 ms 22528 KB Correct.
16 Correct 142 ms 19156 KB Correct.
17 Correct 169 ms 19160 KB Correct.
18 Correct 169 ms 19152 KB Correct.
19 Correct 424 ms 18924 KB Correct.
20 Correct 14 ms 16476 KB Correct.
21 Correct 15 ms 18800 KB Correct.
22 Correct 26 ms 21208 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 19924 KB Correct.
2 Correct 75 ms 21452 KB Correct.
3 Correct 421 ms 65104 KB Correct.
4 Correct 847 ms 23396 KB Correct.
5 Correct 2197 ms 105592 KB Correct.
6 Correct 1057 ms 93972 KB Correct.
7 Correct 996 ms 37460 KB Correct.
8 Correct 1016 ms 21784 KB Correct.
9 Correct 570 ms 21184 KB Correct.
10 Correct 547 ms 23236 KB Correct.
11 Correct 1732 ms 18836 KB Correct.
12 Correct 552 ms 21204 KB Correct.
13 Correct 580 ms 22988 KB Correct.
14 Execution timed out 3033 ms 103824 KB Time limit exceeded
15 Halted 0 ms 0 KB -