oj.uz

답안 #939999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939999 2024-03-07T03:37:48 Z tamir1 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 1875 ms 74392 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
#include <vector>
#define ff first
#define ss second
#define ll long long
const double INF=1e18;
using namespace std;
ll h,i,j;
vector<pair<ll,double>> v[200001];
bitset<200005> vis;
priority_queue<pair<double,ll>> q;
double dp[200001][71],dist;
void dfs(ll a){
	if(a==h) return;
	if(vis[a]) return;
	vis[a]=1;
	for(pair<ll,double> l:v[a]){
		dfs(l.ff);
	}
}
void dijkstra(ll t){
	while(!q.empty()){
		ll a=q.top().ss;
		double d=q.top().ff;
		q.pop();
		if(dp[a][t]!=-1) continue;
		dp[a][t]=-d;
		if(a!=h) for(pair<ll,double> l:v[a]){
			if(dp[l.ff][t]==-1) q.push({d-l.ss,l.ff});
		}
	}
}
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) {
	h=H;
	dist=INF;
	K=min(K,70);
	for(i=0;i<M;i++){
		v[x[i]].push_back({y[i],c[i]});
		v[y[i]].push_back({x[i],c[i]});
	}
	dfs(0);
	q.push({0,0});
	for(i=0;i<N;i++){
		if(vis[i]==1 && arr[i]==0) q.push({0,i});
		for(j=0;j<=K;j++){
			dp[i][j]=-1;
		}
	}
	dijkstra(0);
	for(j=1;j<=K;j++){
		for(i=0;i<N;i++){
			if(vis[i]==1 && arr[i]==2){
				for(pair<ll,double> l:v[i])
				q.push({-1*(dp[i][j-1]/2)-l.ss,l.ff});
			}
		}
		dijkstra(j);
	}
	vis.reset();
	for(i=0;i<N;i++){
		v[i].clear();
	}
	for(j=0;j<=K;j++){
		if(dp[H][j]!=-1) dist=min(dist,dp[H][j]);
	}
	return (dist==INF ? -1 : dist);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 5724 KB Correct.
2 Correct 20 ms 5708 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 8536 KB Correct.
2 Correct 25 ms 8660 KB Correct.
3 Correct 24 ms 8540 KB Correct.
4 Correct 24 ms 8756 KB Correct.
5 Correct 25 ms 8792 KB Correct.
6 Correct 27 ms 13396 KB Correct.
7 Correct 29 ms 13656 KB Correct.
8 Correct 15 ms 19800 KB Correct.
9 Correct 22 ms 6236 KB Correct.
10 Correct 23 ms 6344 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 8792 KB Correct.
2 Correct 27 ms 8536 KB Correct.
3 Correct 31 ms 8536 KB Correct.
4 Correct 26 ms 6228 KB Correct.
5 Correct 26 ms 6236 KB Correct.
6 Correct 11 ms 12888 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 45020 KB Correct.
2 Correct 144 ms 8528 KB Correct.
3 Correct 121 ms 8616 KB Correct.
4 Correct 131 ms 8528 KB Correct.
5 Correct 67 ms 6740 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 8592 KB Correct.
2 Correct 25 ms 8784 KB Correct.
3 Correct 30 ms 8804 KB Correct.
4 Correct 26 ms 14172 KB Correct.
5 Correct 21 ms 6236 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 8708 KB Correct.
2 Correct 23 ms 8536 KB Correct.
3 Correct 45 ms 56916 KB Correct.
4 Correct 18 ms 11352 KB Correct.
5 Correct 24 ms 6236 KB Correct.
6 Correct 29 ms 8796 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 248 ms 8844 KB Correct.
2 Correct 41 ms 8016 KB Correct.
3 Correct 532 ms 68688 KB Correct.
4 Correct 230 ms 22288 KB Correct.
5 Correct 850 ms 36740 KB Correct.
6 Correct 684 ms 21192 KB Correct.
7 Correct 267 ms 24144 KB Correct.
8 Correct 184 ms 10012 KB Correct.
9 Correct 209 ms 8784 KB Correct.
10 Correct 200 ms 8648 KB Correct.
11 Correct 166 ms 9564 KB Correct.
12 Correct 208 ms 8724 KB Correct.
13 Correct 226 ms 8788 KB Correct.
14 Correct 260 ms 38304 KB Correct.
15 Correct 215 ms 17044 KB Correct.
16 Correct 217 ms 8788 KB Correct.
17 Correct 259 ms 8788 KB Correct.
18 Correct 233 ms 8712 KB Correct.
19 Correct 501 ms 9784 KB Correct.
20 Correct 11 ms 5468 KB Correct.
21 Correct 18 ms 7516 KB Correct.
22 Correct 66 ms 8792 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 530 ms 8796 KB Correct.
2 Correct 89 ms 7992 KB Correct.
3 Correct 236 ms 74392 KB Correct.
4 Correct 261 ms 12372 KB Correct.
5 Correct 1875 ms 36804 KB Correct.
6 Correct 1551 ms 21196 KB Correct.
7 Correct 483 ms 32336 KB Correct.
8 Correct 220 ms 9720 KB Correct.
9 Correct 435 ms 8788 KB Correct.
10 Correct 411 ms 8828 KB Correct.
11 Correct 161 ms 6636 KB Correct.
12 Correct 449 ms 8720 KB Correct.
13 Correct 473 ms 8744 KB Correct.
14 Correct 1435 ms 36264 KB Correct.
15 Correct 816 ms 40732 KB Correct.
16 Correct 434 ms 20048 KB Correct.
17 Correct 249 ms 9812 KB Correct.
18 Correct 471 ms 8888 KB Correct.
19 Correct 521 ms 8840 KB Correct.
20 Correct 510 ms 8812 KB Correct.
21 Correct 1129 ms 9644 KB Correct.
22 Correct 18 ms 5516 KB Correct.
23 Correct 37 ms 7516 KB Correct.
24 Correct 143 ms 8796 KB Correct.