Submission #1008245

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1008245	2024-06-26T08:36:35 Z	imarn	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	101244 KB

cyberland

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#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	23 ms	10328 KB	Correct.
2	Correct	22 ms	10328 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	8540 KB	Correct.
2	Correct	18 ms	10588 KB	Correct.
3	Correct	17 ms	8536 KB	Correct.
4	Correct	18 ms	8540 KB	Correct.
5	Correct	22 ms	8540 KB	Correct.
6	Correct	14 ms	10844 KB	Correct.
7	Correct	27 ms	10844 KB	Correct.
8	Correct	11 ms	13404 KB	Correct.
9	Correct	15 ms	8224 KB	Correct.
10	Correct	16 ms	10328 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	8540 KB	Correct.
2	Correct	17 ms	10544 KB	Correct.
3	Correct	17 ms	8540 KB	Correct.
4	Correct	17 ms	10332 KB	Correct.
5	Correct	20 ms	8276 KB	Correct.
6	Correct	6 ms	10584 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	134 ms	23156 KB	Correct.
2	Correct	178 ms	3420 KB	Correct.
3	Correct	144 ms	3420 KB	Correct.
4	Correct	154 ms	3416 KB	Correct.
5	Correct	130 ms	3156 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	6488 KB	Correct.
2	Correct	16 ms	4508 KB	Correct.
3	Correct	17 ms	6488 KB	Correct.
4	Correct	15 ms	11000 KB	Correct.
5	Correct	14 ms	10332 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	3488 KB	Correct.
2	Correct	25 ms	3416 KB	Correct.
3	Correct	61 ms	26808 KB	Correct.
4	Correct	12 ms	6492 KB	Correct.
5	Correct	17 ms	4204 KB	Correct.
6	Correct	16 ms	4440 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	178 ms	4696 KB	Correct.
2	Correct	23 ms	5332 KB	Correct.
3	Correct	561 ms	26480 KB	Correct.
4	Correct	441 ms	19848 KB	Correct.
5	Correct	634 ms	58536 KB	Correct.
6	Correct	256 ms	38072 KB	Correct.
7	Correct	400 ms	19332 KB	Correct.
8	Correct	376 ms	17056 KB	Correct.
9	Correct	167 ms	17104 KB	Correct.
10	Correct	147 ms	17108 KB	Correct.
11	Correct	403 ms	16860 KB	Correct.
12	Correct	166 ms	17108 KB	Correct.
13	Correct	198 ms	17220 KB	Correct.
14	Correct	356 ms	21596 KB	Correct.
15	Correct	420 ms	18392 KB	Correct.
16	Correct	164 ms	17104 KB	Correct.
17	Correct	184 ms	17072 KB	Correct.
18	Correct	180 ms	17100 KB	Correct.
19	Correct	406 ms	16872 KB	Correct.
20	Correct	14 ms	16476 KB	Correct.
21	Correct	15 ms	16728 KB	Correct.
22	Correct	23 ms	18896 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	566 ms	17864 KB	Correct.
2	Correct	77 ms	19412 KB	Correct.
3	Correct	409 ms	63708 KB	Correct.
4	Correct	845 ms	19400 KB	Correct.
5	Correct	2201 ms	101240 KB	Correct.
6	Correct	1085 ms	90228 KB	Correct.
7	Correct	926 ms	33460 KB	Correct.
8	Correct	1063 ms	17868 KB	Correct.
9	Correct	555 ms	19100 KB	Correct.
10	Correct	522 ms	19080 KB	Correct.
11	Correct	1651 ms	16800 KB	Correct.
12	Correct	488 ms	18940 KB	Correct.
13	Correct	547 ms	18888 KB	Correct.
14	Execution timed out	3068 ms	101244 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Submission #1008245

Compilation message