oj.uz

Submission #1008242

# Submission time Handle Problem Language Result Execution time Memory
1008242 2024-06-26T08:35:05 Z imarn Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 97400 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,int>>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 28 ms 10328 KB Correct.
2 Correct 32 ms 8296 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8536 KB Correct.
2 Correct 20 ms 10584 KB Correct.
3 Correct 18 ms 10588 KB Correct.
4 Correct 20 ms 8540 KB Correct.
5 Correct 22 ms 8540 KB Correct.
6 Correct 18 ms 12636 KB Correct.
7 Correct 23 ms 10844 KB Correct.
8 Correct 12 ms 15196 KB Correct.
9 Correct 18 ms 8288 KB Correct.
10 Correct 24 ms 8284 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10328 KB Correct.
2 Correct 19 ms 10588 KB Correct.
3 Correct 21 ms 8588 KB Correct.
4 Correct 19 ms 8284 KB Correct.
5 Correct 20 ms 8284 KB Correct.
6 Correct 6 ms 12376 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 26832 KB Correct.
2 Correct 175 ms 8588 KB Correct.
3 Correct 153 ms 10584 KB Correct.
4 Correct 162 ms 8536 KB Correct.
5 Correct 136 ms 10328 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10588 KB Correct.
2 Correct 17 ms 10588 KB Correct.
3 Correct 17 ms 10588 KB Correct.
4 Correct 18 ms 12892 KB Correct.
5 Correct 16 ms 8280 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10616 KB Correct.
2 Correct 17 ms 10584 KB Correct.
3 Correct 33 ms 28508 KB Correct.
4 Correct 13 ms 12380 KB Correct.
5 Correct 19 ms 10328 KB Correct.
6 Correct 17 ms 10584 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 8796 KB Correct.
2 Correct 25 ms 9176 KB Correct.
3 Correct 567 ms 26312 KB Correct.
4 Correct 406 ms 15056 KB Correct.
5 Correct 621 ms 51776 KB Correct.
6 Correct 320 ms 28856 KB Correct.
7 Correct 378 ms 11472 KB Correct.
8 Correct 414 ms 7312 KB Correct.
9 Correct 159 ms 6864 KB Correct.
10 Correct 154 ms 4972 KB Correct.
11 Correct 403 ms 6844 KB Correct.
12 Correct 156 ms 4836 KB Correct.
13 Correct 165 ms 6872 KB Correct.
14 Correct 338 ms 13260 KB Correct.
15 Correct 405 ms 8920 KB Correct.
16 Correct 160 ms 6944 KB Correct.
17 Correct 187 ms 6800 KB Correct.
18 Correct 184 ms 8912 KB Correct.
19 Correct 434 ms 11088 KB Correct.
20 Correct 13 ms 8280 KB Correct.
21 Correct 14 ms 10732 KB Correct.
22 Correct 25 ms 12752 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 9904 KB Correct.
2 Correct 75 ms 11368 KB Correct.
3 Correct 400 ms 63828 KB Correct.
4 Correct 902 ms 13764 KB Correct.
5 Correct 2358 ms 97400 KB Correct.
6 Correct 1088 ms 82964 KB Correct.
7 Correct 1039 ms 26776 KB Correct.
8 Correct 1032 ms 11736 KB Correct.
9 Correct 536 ms 12996 KB Correct.
10 Correct 532 ms 10980 KB Correct.
11 Correct 1745 ms 10700 KB Correct.
12 Correct 529 ms 12996 KB Correct.
13 Correct 583 ms 10952 KB Correct.
14 Execution timed out 3079 ms 96164 KB Time limit exceeded
15 Halted 0 ms 0 KB -