oj.uz

답안 #749204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
749204 2023-05-27T14:25:29 Z kshitij_sodani 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 2767 ms 176928 KB 
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
 
#include "cyberland.h"
 
#include <vector>
 
vector<pair<int,int>> adj[100001];
long double dist[100001][101];
bool vis[100001][101];
double solve(int n, int m, int k, int x,vector<int> aa,vector<int> bb, vector<int> cc, vector<int> it) {
	for(int i=0;i<n;i++){
		adj[i].clear();
		for(int j=0;j<=min(70,k);j++){
			dist[i][j]=-1;
			vis[i][j]=0;
		}
	}
	for(int i=0;i<m;i++){
		adj[aa[i]].pb({bb[i],cc[i]});
		adj[bb[i]].pb({aa[i],cc[i]});
	}
	dist[0][0]=0;
	vis[0][0]=1;
	/*
	priority_queue<pair<long double,pair<int,int>>> ss;
	
	ss.push({0,{0,0}});*/
	for(int i=0;i<=min(70,k);i++){
		priority_queue<pair<long double,pair<int,int>>> ss;
 
		for(int j=0;j<n;j++){
			if(vis[j][i]==1 and j!=x){
				ss.push({-dist[j][i],{j,i}});
			}
		}
		while(ss.size()){
			pair<long double,pair<int,int>> no=ss.top();
			no.a=-no.a;
			ss.pop();
			if(dist[no.b.a][no.b.b]<no.a){
				continue;
			}
			if(no.b.a==x){
				continue;
			}
			for(auto j:adj[no.b.a]){
				long double mi=no.a+j.b;
				pair<int,int> rr={j.a,no.b.b};
				if(it[j.a]==0){
					mi=0;
				}
				if(vis[rr.a][rr.b]==0 or dist[rr.a][rr.b]>=mi+0.000000001){
					dist[rr.a][rr.b]=mi;
					vis[rr.a][rr.b]=1;
					ss.push({-mi,{rr.a,rr.b}});
				}
				if(it[j.a]==2){
					mi/=(long double)2;
					rr.b+=1;
					if(rr.b>70){
						continue;
					}
					if(vis[rr.a][rr.b]==0 or dist[rr.a][rr.b]>=mi+0.000000001){
						dist[rr.a][rr.b]=mi;
						vis[rr.a][rr.b]=1;
						//ss.push({-mi,{rr.a,rr.b}});
					}
				}
			}
		}
	}
 
	long double ans=-1;
	int st=0;
	for(int i=0;i<=min(k,70);i++){
		if(vis[x][i]==1){
			if(st==0){
				st=1;
				ans=dist[x][i];
			}
			if(dist[x][i]<=ans-0.0000001){
				ans=dist[x][i];
			}
		}
	}
 
 
 
 
 
 
 
	return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2772 KB Correct.
2 Correct 26 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 4508 KB Correct.
2 Correct 35 ms 4452 KB Correct.
3 Correct 32 ms 4496 KB Correct.
4 Correct 33 ms 4460 KB Correct.
5 Correct 32 ms 4476 KB Correct.
6 Correct 40 ms 19868 KB Correct.
7 Correct 48 ms 19556 KB Correct.
8 Correct 35 ms 37076 KB Correct.
9 Correct 29 ms 2892 KB Correct.
10 Correct 31 ms 2900 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 4428 KB Correct.
2 Correct 37 ms 4448 KB Correct.
3 Correct 32 ms 4436 KB Correct.
4 Correct 31 ms 2880 KB Correct.
5 Correct 31 ms 2896 KB Correct.
6 Correct 15 ms 16724 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 104568 KB Correct.
2 Correct 173 ms 4536 KB Correct.
3 Correct 150 ms 4428 KB Correct.
4 Correct 158 ms 4404 KB Correct.
5 Correct 103 ms 2868 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 4564 KB Correct.
2 Correct 30 ms 4504 KB Correct.
3 Correct 30 ms 4436 KB Correct.
4 Correct 39 ms 19768 KB Correct.
5 Correct 28 ms 2888 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 4436 KB Correct.
2 Correct 28 ms 4444 KB Correct.
3 Correct 98 ms 134836 KB Correct.
4 Correct 29 ms 14960 KB Correct.
5 Correct 28 ms 2772 KB Correct.
6 Correct 32 ms 4448 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 198 ms 4536 KB Correct.
2 Correct 32 ms 5684 KB Correct.
3 Correct 1151 ms 169316 KB Correct.
4 Correct 563 ms 40460 KB Correct.
5 Correct 923 ms 68888 KB Correct.
6 Correct 364 ms 24688 KB Correct.
7 Correct 610 ms 44132 KB Correct.
8 Correct 408 ms 8884 KB Correct.
9 Correct 158 ms 4524 KB Correct.
10 Correct 153 ms 4496 KB Correct.
11 Correct 367 ms 4904 KB Correct.
12 Correct 185 ms 4544 KB Correct.
13 Correct 178 ms 4584 KB Correct.
14 Correct 617 ms 83828 KB Correct.
15 Correct 459 ms 24524 KB Correct.
16 Correct 159 ms 4448 KB Correct.
17 Correct 203 ms 4544 KB Correct.
18 Correct 188 ms 4640 KB Correct.
19 Correct 543 ms 4464 KB Correct.
20 Correct 12 ms 2772 KB Correct.
21 Correct 16 ms 4368 KB Correct.
22 Correct 25 ms 4692 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 399 ms 4548 KB Correct.
2 Correct 57 ms 5708 KB Correct.
3 Correct 952 ms 176928 KB Correct.
4 Correct 600 ms 13684 KB Correct.
5 Correct 2081 ms 68976 KB Correct.
6 Correct 648 ms 24692 KB Correct.
7 Correct 1063 ms 65088 KB Correct.
8 Correct 510 ms 5252 KB Correct.
9 Correct 303 ms 4704 KB Correct.
10 Correct 316 ms 4524 KB Correct.
11 Correct 292 ms 2980 KB Correct.
12 Correct 340 ms 4552 KB Correct.
13 Correct 362 ms 4636 KB Correct.
14 Correct 2767 ms 71784 KB Correct.
15 Correct 2367 ms 89012 KB Correct.
16 Correct 914 ms 33748 KB Correct.
17 Correct 591 ms 8984 KB Correct.
18 Correct 367 ms 4564 KB Correct.
19 Correct 395 ms 4584 KB Correct.
20 Correct 377 ms 4428 KB Correct.
21 Correct 1103 ms 4480 KB Correct.
22 Correct 29 ms 2772 KB Correct.
23 Correct 27 ms 4364 KB Correct.
24 Correct 53 ms 4692 KB Correct.