oj.uz

Submission #1008238

# Submission time Handle Problem Language Result Execution time Memory
1008238 2024-06-26T08:34:11 Z imarn Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 99952 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};
int pr[mxn]{0};
int get(int r){
    return pr[r]==r?r:pr[r]=get(pr[r]);
}
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){
    iota(pr,pr+N,0);
    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]});
        if(x[i]==H||y[i]==H)continue;
        pr[get(x[i])]=get(y[i]);
    }
    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&&get(i)==get(0))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();
    return (ans>=1e17?-1:ans);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12632 KB Correct.
2 Correct 11 ms 12636 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12636 KB Correct.
2 Correct 17 ms 12636 KB Correct.
3 Correct 17 ms 12636 KB Correct.
4 Correct 20 ms 14680 KB Correct.
5 Correct 18 ms 12792 KB Correct.
6 Correct 18 ms 14684 KB Correct.
7 Correct 22 ms 14724 KB Correct.
8 Correct 12 ms 16956 KB Correct.
9 Correct 17 ms 12380 KB Correct.
10 Correct 17 ms 14424 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12632 KB Correct.
2 Correct 19 ms 12788 KB Correct.
3 Correct 18 ms 12688 KB Correct.
4 Correct 19 ms 12380 KB Correct.
5 Correct 19 ms 12380 KB Correct.
6 Correct 7 ms 14428 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 28232 KB Correct.
2 Correct 173 ms 14928 KB Correct.
3 Correct 148 ms 12884 KB Correct.
4 Correct 162 ms 12724 KB Correct.
5 Correct 138 ms 14424 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12632 KB Correct.
2 Correct 18 ms 14684 KB Correct.
3 Correct 20 ms 12632 KB Correct.
4 Correct 22 ms 14708 KB Correct.
5 Correct 24 ms 12380 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3420 KB Correct.
2 Correct 30 ms 3316 KB Correct.
3 Correct 45 ms 26704 KB Correct.
4 Correct 23 ms 5212 KB Correct.
5 Correct 16 ms 2908 KB Correct.
6 Correct 19 ms 3420 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 3488 KB Correct.
2 Correct 34 ms 4056 KB Correct.
3 Correct 626 ms 26820 KB Correct.
4 Correct 454 ms 19872 KB Correct.
5 Correct 746 ms 58284 KB Correct.
6 Correct 346 ms 38068 KB Correct.
7 Correct 441 ms 19400 KB Correct.
8 Correct 435 ms 17116 KB Correct.
9 Correct 172 ms 17100 KB Correct.
10 Correct 179 ms 17272 KB Correct.
11 Correct 399 ms 17024 KB Correct.
12 Correct 161 ms 17368 KB Correct.
13 Correct 176 ms 17088 KB Correct.
14 Correct 360 ms 21764 KB Correct.
15 Correct 429 ms 18392 KB Correct.
16 Correct 179 ms 13268 KB Correct.
17 Correct 197 ms 13268 KB Correct.
18 Correct 192 ms 13256 KB Correct.
19 Correct 429 ms 13024 KB Correct.
20 Correct 14 ms 12632 KB Correct.
21 Correct 17 ms 13144 KB Correct.
22 Correct 26 ms 15052 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 6092 KB Correct.
2 Correct 75 ms 7616 KB Correct.
3 Correct 470 ms 61776 KB Correct.
4 Correct 976 ms 15812 KB Correct.
5 Correct 2313 ms 99952 KB Correct.
6 Correct 1126 ms 86684 KB Correct.
7 Correct 981 ms 30220 KB Correct.
8 Correct 1025 ms 13900 KB Correct.
9 Correct 540 ms 15048 KB Correct.
10 Correct 526 ms 15300 KB Correct.
11 Correct 1792 ms 14860 KB Correct.
12 Correct 538 ms 15192 KB Correct.
13 Correct 599 ms 15124 KB Correct.
14 Execution timed out 3054 ms 99936 KB Time limit exceeded
15 Halted 0 ms 0 KB -