Submission #932026

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
932026	2024-02-22T20:11:50 Z	Edu175	Cyberland (APIO23_cyberland)	C++17	100 / 100	1879 ms	132176 KB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,apio=b;i<apio;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto slkdh:v)cout<<slkdh<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<ll,pair<ld,ll>> node;
const ll MAXN=1e5+5;

vector<pair<ll,ll>>g[MAXN];
ll h;
ll vis[MAXN];
void dfs(ll x){
	vis[x]=1;
	for(auto [y,sg]:g[x])if(!vis[y]&&y!=h)dfs(y);
}
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) {
    ll n=N,m=M,k=K;
    k=min(k,(ll)70);
    h=H;
    vector<ll>a(n);
    fore(i,0,n)a[i]=arr[i];
    fore(i,0,n){
    	g[i].clear();
    	vis[i]=0;
    }
    fore(i,0,m){
    	g[x[i]].pb({y[i],c[i]});
    	g[y[i]].pb({x[i],c[i]});
    }
    dfs(0);
    ld d[n][k+5];
    fore(i,0,n)fore(j,0,k+5)d[i][j]=-1;
    priority_queue<node,vector<node>,greater<node>>pq;
    a[0]=0;
    fore(i,0,n)if(vis[i]&&!a[i]){
    	pq.push({0,{0,i}});
    	d[i][0]=0;
    }
    ld res=-1;
    while(SZ(pq)){
    	auto [u,par]=pq.top(); pq.pop();// w=-w;
    	auto [w,x]=par;
    	if(d[x][u]<w)continue;
    	if(x==h){
    		if(res==-1||w<res)res=w;
    		continue;
    	}
    	//cout<<x<<" "<<u<<": "<<w<<"\n";
    	for(auto [y,w]:g[x]){
    		ld nd=d[x][u]+w;//double(1ll<<u);
    		if(d[y][u]<-0.5||nd<d[y][u])
    			d[y][u]=nd,pq.push({u,{nd,y}});
    		if(a[y]==2){
    			nd/=2.0;
    			ll v=u+1;
    			if(v>k)continue;
    			if(d[y][v]<-0.5||nd<d[y][v])
    				d[y][v]=nd,pq.push({v,{nd,y}});
    		}
    	}
    }
    return res;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	3420 KB	Correct.
2	Correct	18 ms	3420 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	4188 KB	Correct.
2	Correct	28 ms	3932 KB	Correct.
3	Correct	26 ms	4092 KB	Correct.
4	Correct	27 ms	4136 KB	Correct.
5	Correct	33 ms	4188 KB	Correct.
6	Correct	29 ms	9780 KB	Correct.
7	Correct	34 ms	9820 KB	Correct.
8	Correct	23 ms	16220 KB	Correct.
9	Correct	26 ms	3676 KB	Correct.
10	Correct	24 ms	3420 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	4184 KB	Correct.
2	Correct	27 ms	4204 KB	Correct.
3	Correct	29 ms	4184 KB	Correct.
4	Correct	31 ms	3520 KB	Correct.
5	Correct	30 ms	3420 KB	Correct.
6	Correct	9 ms	9116 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	180 ms	41296 KB	Correct.
2	Correct	179 ms	4124 KB	Correct.
3	Correct	160 ms	5532 KB	Correct.
4	Correct	164 ms	5372 KB	Correct.
5	Correct	113 ms	4256 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	4252 KB	Correct.
2	Correct	24 ms	4188 KB	Correct.
3	Correct	24 ms	4100 KB	Correct.
4	Correct	26 ms	10136 KB	Correct.
5	Correct	22 ms	3416 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	4196 KB	Correct.
2	Correct	21 ms	4184 KB	Correct.
3	Correct	60 ms	51940 KB	Correct.
4	Correct	19 ms	8472 KB	Correct.
5	Correct	23 ms	3420 KB	Correct.
6	Correct	23 ms	4312 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	202 ms	4204 KB	Correct.
2	Correct	35 ms	4668 KB	Correct.
3	Correct	843 ms	45332 KB	Correct.
4	Correct	387 ms	16980 KB	Correct.
5	Correct	739 ms	35016 KB	Correct.
6	Correct	320 ms	17868 KB	Correct.
7	Correct	405 ms	16300 KB	Correct.
8	Correct	299 ms	7248 KB	Correct.
9	Correct	169 ms	5292 KB	Correct.
10	Correct	159 ms	5252 KB	Correct.
11	Correct	278 ms	5972 KB	Correct.
12	Correct	175 ms	5100 KB	Correct.
13	Correct	185 ms	5304 KB	Correct.
14	Correct	354 ms	18072 KB	Correct.
15	Correct	324 ms	9468 KB	Correct.
16	Correct	170 ms	5200 KB	Correct.
17	Correct	215 ms	5200 KB	Correct.
18	Correct	195 ms	5200 KB	Correct.
19	Correct	495 ms	5968 KB	Correct.
20	Correct	11 ms	3420 KB	Correct.
21	Correct	14 ms	4116 KB	Correct.
22	Correct	25 ms	5208 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	436 ms	5712 KB	Correct.
2	Correct	63 ms	5724 KB	Correct.
3	Correct	1164 ms	132176 KB	Correct.
4	Correct	431 ms	10988 KB	Correct.
5	Correct	1762 ms	58056 KB	Correct.
6	Correct	758 ms	24528 KB	Correct.
7	Correct	765 ms	31656 KB	Correct.
8	Correct	423 ms	7248 KB	Correct.
9	Correct	348 ms	5704 KB	Correct.
10	Correct	343 ms	5652 KB	Correct.
11	Correct	223 ms	4728 KB	Correct.
12	Correct	392 ms	5712 KB	Correct.
13	Correct	381 ms	5792 KB	Correct.
14	Correct	1879 ms	57444 KB	Correct.
15	Correct	1601 ms	68336 KB	Correct.
16	Correct	665 ms	26888 KB	Correct.
17	Correct	458 ms	9808 KB	Correct.
18	Correct	383 ms	5972 KB	Correct.
19	Correct	429 ms	5968 KB	Correct.
20	Correct	430 ms	5752 KB	Correct.
21	Correct	1091 ms	6884 KB	Correct.
22	Correct	23 ms	3644 KB	Correct.
23	Correct	30 ms	4648 KB	Correct.
24	Correct	52 ms	5468 KB	Correct.

Submission #932026

Compilation message