oj.uz

Submission #1008221

# Submission time Handle Problem Language Result Execution time Memory
1008221 2024-06-26T08:29:28 Z imarn Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 103800 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+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],i}),g[y[i]].pb({x[i],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+c[v.s])d[u.s.f][v.f]=u.f+c[v.s],q.push({u.f+c[v.s],{u.s.f,v.f}});
            if(arr[v.f]==2&&u.s.f<K){
                double t = (u.f+c[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 26 ms 20500 KB Correct.
2 Correct 23 ms 16440 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 18524 KB Correct.
2 Correct 20 ms 18664 KB Correct.
3 Correct 26 ms 18880 KB Correct.
4 Correct 19 ms 18524 KB Correct.
5 Correct 20 ms 18520 KB Correct.
6 Correct 16 ms 20060 KB Correct.
7 Correct 22 ms 20056 KB Correct.
8 Correct 17 ms 23388 KB Correct.
9 Correct 26 ms 20508 KB Correct.
10 Correct 26 ms 20508 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 18520 KB Correct.
2 Correct 17 ms 18524 KB Correct.
3 Correct 17 ms 18904 KB Correct.
4 Correct 20 ms 16440 KB Correct.
5 Correct 22 ms 18472 KB Correct.
6 Correct 6 ms 18012 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 29132 KB Correct.
2 Correct 206 ms 18780 KB Correct.
3 Correct 133 ms 18744 KB Correct.
4 Correct 167 ms 18520 KB Correct.
5 Correct 129 ms 18264 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 18524 KB Correct.
2 Correct 18 ms 18556 KB Correct.
3 Correct 28 ms 16652 KB Correct.
4 Correct 19 ms 18408 KB Correct.
5 Correct 15 ms 18468 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16668 KB Correct.
2 Correct 16 ms 20568 KB Correct.
3 Correct 41 ms 30292 KB Correct.
4 Correct 16 ms 19804 KB Correct.
5 Correct 18 ms 18468 KB Correct.
6 Correct 24 ms 20572 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 18892 KB Correct.
2 Correct 24 ms 19160 KB Correct.
3 Correct 551 ms 27072 KB Correct.
4 Correct 433 ms 22940 KB Correct.
5 Correct 678 ms 59556 KB Correct.
6 Correct 318 ms 41660 KB Correct.
7 Correct 447 ms 20784 KB Correct.
8 Correct 407 ms 21068 KB Correct.
9 Correct 159 ms 21192 KB Correct.
10 Correct 172 ms 19104 KB Correct.
11 Correct 410 ms 18868 KB Correct.
12 Correct 148 ms 19160 KB Correct.
13 Correct 169 ms 18936 KB Correct.
14 Correct 351 ms 21712 KB Correct.
15 Correct 391 ms 20384 KB Correct.
16 Correct 144 ms 19148 KB Correct.
17 Correct 187 ms 17112 KB Correct.
18 Correct 184 ms 19148 KB Correct.
19 Correct 412 ms 18904 KB Correct.
20 Correct 14 ms 18524 KB Correct.
21 Correct 14 ms 18792 KB Correct.
22 Correct 30 ms 18936 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 20084 KB Correct.
2 Correct 77 ms 21440 KB Correct.
3 Correct 402 ms 63484 KB Correct.
4 Correct 873 ms 23208 KB Correct.
5 Correct 2413 ms 103800 KB Correct.
6 Correct 1204 ms 92032 KB Correct.
7 Correct 961 ms 36604 KB Correct.
8 Correct 951 ms 19732 KB Correct.
9 Correct 489 ms 19140 KB Correct.
10 Correct 500 ms 22996 KB Correct.
11 Correct 1657 ms 20828 KB Correct.
12 Correct 478 ms 19136 KB Correct.
13 Correct 534 ms 20928 KB Correct.
14 Execution timed out 3021 ms 101264 KB Time limit exceeded
15 Halted 0 ms 0 KB -