oj.uz

Submission #933557

# Submission time Handle Problem Language Result Execution time Memory
933557 2024-02-25T21:53:12 Z JuanJL Cyberland (APIO23_cyberland) C++17
100 / 100
 1253 ms 71504 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
 
#define fst first 
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(v) cout<<"Line("<<__LINE__<<"): "<<#v<<" = "<<v<<'\n';
#define pi pair<int,int>
#define pll pair<ll,ll>
typedef int ll;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_multiset;
 
ll n,m,k,h;
vector<pll> adj[(ll)1e5+5];
ll type[(ll)1e5+5];
bool disp[(ll)1e5+5];
 
void dfs(ll nd){
	if(disp[nd]) return;
	disp[nd]=1;
	if(nd==h) return;
	for(auto i:adj[nd]) dfs(i.fst);
}
 
double Dijkstra(){
	vector<vector<double>> dist(n+1,vector<double>(k+1,-1));
	priority_queue<pair<double,pair<double,ll>>> pq;
	pq.push({0,{0,0}});
	dist[0][0]=0;
	forn(i,0,n){
		if(type[i]==0&&disp[i]){
			pq.push({0,{0,i}});
			dist[i][0]=0;
			//forn(j,0,k+1) dist[i][j]=0;
		}
	}
	type[0]=0;
	double cost;
	ll nd;
	ll p2;
	ll ndV;
	double nCost;
	while(!pq.empty()){
		cost = pq.top().snd.fst*-1;
		nd = pq.top().snd.snd;
		p2 = pq.top().fst*-1;
		pq.pop();
		if(cost>dist[nd][p2]) continue;
		
		if(nd==h) continue;
		
		for(auto i:adj[nd]){
			ndV = i.fst;
			nCost = i.snd+cost;
			if(type[ndV]==0) continue;
			if(nCost<dist[ndV][p2]||dist[ndV][p2]==-1){
				dist[ndV][p2]=nCost;
				pq.push({p2*-1,{dist[ndV][p2]*-1,ndV}});
			}
			if(type[ndV]==2&&p2+1<min((ll)k+1,(ll)k+1)){
				nCost/=2;
				if(nCost<dist[ndV][p2+1]||dist[ndV][p2+1]==-1){
					dist[ndV][p2+1]=nCost;
					pq.push({(p2+1)*-1,{dist[ndV][p2+1]*-1,ndV}});					
				}
			}
		}
	}
	double res = -1;
	forn(i,0,k+1) if(dist[h][i]!=-1&&(res>dist[h][i]||res==-1))  res = dist[h][i];
	return (double)res;
}	
 
 
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){
	n=N;m=M;k=min((ll)K,(ll)70);h=H;	
	forn(i,0,n) disp[i]=0,adj[i].clear(),type[i]=arr[i];
	forn(i,0,m)	adj[x[i]].pb({y[i],c[i]}),adj[y[i]].pb({x[i],c[i]});
	dfs(0);
	return Dijkstra();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3164 KB Correct.
2 Correct 15 ms 3164 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3420 KB Correct.
2 Correct 24 ms 3472 KB Correct.
3 Correct 23 ms 3420 KB Correct.
4 Correct 24 ms 3504 KB Correct.
5 Correct 27 ms 3520 KB Correct.
6 Correct 23 ms 6620 KB Correct.
7 Correct 30 ms 6568 KB Correct.
8 Correct 14 ms 10076 KB Correct.
9 Correct 22 ms 3164 KB Correct.
10 Correct 22 ms 3160 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3472 KB Correct.
2 Correct 26 ms 3520 KB Correct.
3 Correct 25 ms 3800 KB Correct.
4 Correct 25 ms 3164 KB Correct.
5 Correct 24 ms 3164 KB Correct.
6 Correct 6 ms 6048 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 23584 KB Correct.
2 Correct 82 ms 3416 KB Correct.
3 Correct 73 ms 3628 KB Correct.
4 Correct 76 ms 3468 KB Correct.
5 Correct 49 ms 3208 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3576 KB Correct.
2 Correct 22 ms 3420 KB Correct.
3 Correct 22 ms 3548 KB Correct.
4 Correct 22 ms 6560 KB Correct.
5 Correct 19 ms 3160 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3540 KB Correct.
2 Correct 21 ms 3536 KB Correct.
3 Correct 43 ms 29012 KB Correct.
4 Correct 17 ms 5604 KB Correct.
5 Correct 21 ms 3164 KB Correct.
6 Correct 26 ms 3544 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 3484 KB Correct.
2 Correct 15 ms 3676 KB Correct.
3 Correct 624 ms 27216 KB Correct.
4 Correct 267 ms 9360 KB Correct.
5 Correct 333 ms 19656 KB Correct.
6 Correct 153 ms 10832 KB Correct.
7 Correct 275 ms 9116 KB Correct.
8 Correct 213 ms 4072 KB Correct.
9 Correct 81 ms 3744 KB Correct.
10 Correct 79 ms 3520 KB Correct.
11 Correct 189 ms 3592 KB Correct.
12 Correct 85 ms 3536 KB Correct.
13 Correct 86 ms 3564 KB Correct.
14 Correct 267 ms 10732 KB Correct.
15 Correct 249 ms 5496 KB Correct.
16 Correct 84 ms 3528 KB Correct.
17 Correct 101 ms 3764 KB Correct.
18 Correct 93 ms 3544 KB Correct.
19 Correct 222 ms 3420 KB Correct.
20 Correct 6 ms 3164 KB Correct.
21 Correct 7 ms 3416 KB Correct.
22 Correct 13 ms 3972 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 4048 KB Correct.
2 Correct 29 ms 4188 KB Correct.
3 Correct 740 ms 71504 KB Correct.
4 Correct 314 ms 5736 KB Correct.
5 Correct 683 ms 30920 KB Correct.
6 Correct 320 ms 14164 KB Correct.
7 Correct 525 ms 15960 KB Correct.
8 Correct 277 ms 4076 KB Correct.
9 Correct 153 ms 3900 KB Correct.
10 Correct 154 ms 3860 KB Correct.
11 Correct 129 ms 3408 KB Correct.
12 Correct 164 ms 3812 KB Correct.
13 Correct 187 ms 3844 KB Correct.
14 Correct 1253 ms 30492 KB Correct.
15 Correct 992 ms 37804 KB Correct.
16 Correct 477 ms 15708 KB Correct.
17 Correct 318 ms 7320 KB Correct.
18 Correct 165 ms 4852 KB Correct.
19 Correct 195 ms 4892 KB Correct.
20 Correct 187 ms 4848 KB Correct.
21 Correct 460 ms 5712 KB Correct.
22 Correct 9 ms 3160 KB Correct.
23 Correct 14 ms 3688 KB Correct.
24 Correct 26 ms 4420 KB Correct.