oj.uz

Submission #1008178

# Submission time Handle Problem Language Result Execution time Memory
1008178 2024-06-26T08:11:11 Z imarn Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 127644 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);
    }
}
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;
                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 25 ms 28504 KB Correct.
2 Correct 25 ms 28504 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28764 KB Correct.
2 Correct 20 ms 28764 KB Correct.
3 Correct 19 ms 28764 KB Correct.
4 Correct 20 ms 28728 KB Correct.
5 Correct 22 ms 28764 KB Correct.
6 Correct 19 ms 29444 KB Correct.
7 Correct 23 ms 29580 KB Correct.
8 Correct 13 ms 30300 KB Correct.
9 Correct 19 ms 28660 KB Correct.
10 Correct 20 ms 28508 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 28764 KB Correct.
3 Correct 20 ms 28764 KB Correct.
4 Correct 22 ms 28508 KB Correct.
5 Correct 21 ms 28508 KB Correct.
6 Correct 7 ms 29276 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 35524 KB Correct.
2 Correct 159 ms 28864 KB Correct.
3 Correct 132 ms 28760 KB Correct.
4 Correct 134 ms 28764 KB Correct.
5 Correct 125 ms 28648 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28760 KB Correct.
2 Correct 18 ms 28856 KB Correct.
3 Correct 17 ms 28764 KB Correct.
4 Correct 21 ms 29880 KB Correct.
5 Correct 20 ms 28508 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28760 KB Correct.
2 Correct 16 ms 28764 KB Correct.
3 Correct 29 ms 35164 KB Correct.
4 Correct 15 ms 29532 KB Correct.
5 Correct 17 ms 28632 KB Correct.
6 Correct 17 ms 28904 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 29036 KB Correct.
2 Correct 25 ms 29276 KB Correct.
3 Correct 536 ms 28408 KB Correct.
4 Correct 405 ms 27168 KB Correct.
5 Correct 584 ms 68524 KB Correct.
6 Correct 276 ms 51996 KB Correct.
7 Correct 399 ms 28876 KB Correct.
8 Correct 416 ms 29176 KB Correct.
9 Correct 166 ms 29288 KB Correct.
10 Correct 162 ms 29280 KB Correct.
11 Correct 404 ms 28972 KB Correct.
12 Correct 170 ms 29164 KB Correct.
13 Correct 180 ms 29252 KB Correct.
14 Correct 364 ms 31816 KB Correct.
15 Correct 434 ms 30208 KB Correct.
16 Correct 156 ms 29140 KB Correct.
17 Correct 185 ms 29260 KB Correct.
18 Correct 189 ms 29140 KB Correct.
19 Correct 404 ms 28932 KB Correct.
20 Correct 16 ms 28764 KB Correct.
21 Correct 16 ms 28884 KB Correct.
22 Correct 31 ms 31188 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 56496 KB Correct.
2 Correct 84 ms 57512 KB Correct.
3 Correct 387 ms 65104 KB Correct.
4 Correct 925 ms 56780 KB Correct.
5 Correct 2432 ms 127644 KB Correct.
6 Correct 1254 ms 127032 KB Correct.
7 Correct 1143 ms 65976 KB Correct.
8 Correct 1074 ms 56120 KB Correct.
9 Correct 571 ms 57540 KB Correct.
10 Correct 584 ms 57544 KB Correct.
11 Correct 1864 ms 55380 KB Correct.
12 Correct 553 ms 57292 KB Correct.
13 Correct 566 ms 57284 KB Correct.
14 Execution timed out 3081 ms 126500 KB Time limit exceeded
15 Halted 0 ms 0 KB -