oj.uz

Submission #937664

# Submission time Handle Problem Language Result Execution time Memory
937664 2024-03-04T10:19:47 Z Baytoro Cyberland (APIO23_cyberland) C++17
97 / 100
 1976 ms 95944 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
//#include "stub.cpp"

using namespace std;

#define ll long long
//#define int ll
#define pb push_back

#define tt pair<long double,pair<int,int>>
#define fr first
#define sc second.first
#define tr second.second

const ll N1=1e5+5,INF=1e18;
long double dist[N1][33];
vector<pair<int,int>> g[N1];
int a[N1];
int used[N1];
void djks(int x, int h, int n){
	priority_queue<tt,vector<tt>,greater<tt>> pq;
	for(int i=0;i<n;i++){
		if(used[i] && (i==0 || a[i]==0)){
			pq.push({0,{i,0}});
			dist[i][0]=0;
		}
	}
	while(!pq.empty()){
		tt tmp=pq.top();
		pq.pop();
		int cur=tmp.sc,t=tmp.tr;
		if(cur==h) continue;
		if(abs(dist[cur][t]-tmp.fr)>1e-9) continue;
		for(auto it: g[cur]){
			if(dist[it.first][t]>dist[cur][t]+it.second){
				dist[it.first][t]=dist[cur][t]+it.second;
				pq.push({dist[it.first][t],{it.first,t}});
			}
			if(t==30) continue;
			if(a[it.first]==2){
				if(dist[it.first][t+1]>(dist[cur][t]+it.second)/2){
					dist[it.first][t+1]=(dist[cur][t]+it.second)/2;
					pq.push({dist[it.first][t+1],{it.first,t+1}});
				}
			}
		}
	}
}
void dfs(int x, int h){
	
	used[x]=1;
	if(x==h) return;
	for(auto it: g[x]){
		if(!used[it.first]) 
			dfs(it.first,h);
	}
}
double solve(int n, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	for(int i=0;i<n;i++){
		for(int j=0;j<=31;j++)
			dist[i][j]=INF;
		g[i].clear();
		used[i]=0;
	}
	for(int i=0;i<M;i++){
		g[x[i]].pb({y[i],c[i]});
		g[y[i]].pb({x[i],c[i]});
	}
	for(int i=0;i<n;i++)
		a[i]=arr[i];
	dfs(0,H);
	if(!used[H]) return -1;
	djks(0,H,n);
	long double ans=INF;
	for(int i=0;i<=K;i++){
		ans=min(ans,dist[H][i]);
	}
	if(ans==INF) return -1;
	else return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4700 KB Correct.
2 Correct 22 ms 4824 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4704 KB Correct.
2 Correct 33 ms 5516 KB Correct.
3 Correct 29 ms 5336 KB Correct.
4 Correct 37 ms 5468 KB Correct.
5 Correct 32 ms 5456 KB Correct.
6 Correct 27 ms 10072 KB Correct.
7 Correct 37 ms 10332 KB Correct.
8 Correct 18 ms 16732 KB Correct.
9 Correct 28 ms 5208 KB Correct.
10 Correct 28 ms 5204 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4696 KB Correct.
2 Correct 32 ms 4696 KB Correct.
3 Correct 31 ms 4696 KB Correct.
4 Correct 32 ms 4440 KB Correct.
5 Correct 30 ms 5212 KB Correct.
6 Correct 8 ms 9688 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 48160 KB Correct.
2 Correct 460 ms 6188 KB Correct.
3 Correct 382 ms 6388 KB Correct.
4 Correct 413 ms 6376 KB Correct.
5 Correct 337 ms 5608 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4748 KB Correct.
2 Correct 39 ms 5432 KB Correct.
3 Correct 27 ms 5716 KB Correct.
4 Correct 37 ms 10456 KB Correct.
5 Correct 28 ms 5348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4700 KB Correct.
2 Correct 25 ms 4744 KB Correct.
3 Correct 50 ms 48724 KB Correct.
4 Correct 20 ms 9564 KB Correct.
5 Correct 26 ms 4444 KB Correct.
6 Correct 26 ms 4700 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 6672 KB Correct.
2 Correct 59 ms 8324 KB Correct.
3 Correct 1933 ms 71292 KB Correct.
4 Correct 1976 ms 20832 KB Correct.
5 Correct 1653 ms 95944 KB Correct.
6 Correct 768 ms 83364 KB Correct.
7 Correct 1682 ms 22860 KB Correct.
8 Correct 1756 ms 9552 KB Correct.
9 Correct 325 ms 8236 KB Correct.
10 Correct 309 ms 7540 KB Correct.
11 Correct 1671 ms 7020 KB Correct.
12 Correct 364 ms 7508 KB Correct.
13 Correct 408 ms 7652 KB Correct.
14 Correct 1963 ms 48700 KB Correct.
15 Correct 1625 ms 15592 KB Correct.
16 Correct 335 ms 7536 KB Correct.
17 Correct 433 ms 7712 KB Correct.
18 Correct 377 ms 7288 KB Correct.
19 Correct 895 ms 8300 KB Correct.
20 Correct 27 ms 5320 KB Correct.
21 Correct 25 ms 5724 KB Correct.
22 Correct 54 ms 9272 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 435 ms 6592 KB Wrong Answer.
2 Halted 0 ms 0 KB -