oj.uz

답안 #926910

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
926910 2024-02-14T04:15:03 Z Wansur 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 1183 ms 100180 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
  
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
 
using namespace std;
typedef long long ll;
const int mx=1e5+12;
 
vector<pair<int,int>> g[mx];
double d[mx][101];
bool was[mx][101];
bool used[mx];
 
struct node{
	int v,x;
	double w;
	friend bool operator <(node a,node b){
        return a.w > b.w;
    }
};
 
void dfs(int v){
	used[v]=1;
	for(auto to:g[v]){
		if(!used[to.f]){
			dfs(to.f);
		}
	}
}
 
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
	k=min(k,67);
	for(int i=0;i<n;i++){
		g[i].clear();
		used[i]=0;
	}
	for(int i=0;i<m;i++){
		g[x[i]].push_back({y[i],c[i]});
		g[y[i]].push_back({x[i],c[i]});
	}
	dfs(0);
	if(!used[h]){
		return -1;
	}
	for(int i=0;i<n;i++){
		for(int x=0;x<=k+1;x++){
			d[i][x]=1e18;
			was[i][x]=0;
		}
		used[i]=0;
	}
	used[h]=1;
	dfs(0);
	priority_queue<node> s;
	d[0][0]=0;
	s.push({0,0,0});
	for(int i=0;i<n;i++){
		if(used[i] && arr[i]==0){
			d[i][0]=0;
			s.push({i,0,0});
		}
	}
	vector<pair<int,int>> q;
	for(int x=0;x<=k;x++){
		while(s.size()){
			int v=s.top().v,x=s.top().x;
			double w=s.top().w;
			s.pop();
			if(v==h)continue;
			if(w>d[v][x]){
				continue;
			}
			for(const auto &To:g[v]){
				if(d[To.f][x]>d[v][x]+To.s){
					d[To.f][x]=d[v][x]+To.s;
					s.push({To.f,x,d[To.f][x]});
				}
				if(x<k && d[To.f][x+1]>d[v][x]/2+To.s && arr[v]==2){
					d[To.f][x+1]=d[v][x]/2+To.s;
					q.push_back({To.f,x+1});
				}
			}
		}
		for(auto x:q){
			if(was[x.f][x.s])continue;
			was[x.f][x.s]=1;
			s.push({x.f,x.s,d[x.f][x.s]});
		}
	}
	double ans=1e18;
	for(int x=k;x>=0;x--){
		if(d[h][x]>=1e18)continue;
		ans=min(ans,d[h][x]);
		if(arr[h]==2 && x>0 && d[h][x-1]<2e14)ans=min(ans,d[h][x-1]/(double)2.0);
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 5464 KB Correct.
2 Correct 17 ms 5552 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 9836 KB Correct.
2 Correct 22 ms 9820 KB Correct.
3 Correct 21 ms 9764 KB Correct.
4 Correct 22 ms 9820 KB Correct.
5 Correct 22 ms 9800 KB Correct.
6 Correct 25 ms 16440 KB Correct.
7 Correct 26 ms 16472 KB Correct.
8 Correct 15 ms 25500 KB Correct.
9 Correct 20 ms 5564 KB Correct.
10 Correct 19 ms 5468 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 9816 KB Correct.
2 Correct 22 ms 9816 KB Correct.
3 Correct 21 ms 10072 KB Correct.
4 Correct 21 ms 5468 KB Correct.
5 Correct 21 ms 5464 KB Correct.
6 Correct 7 ms 14428 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 66060 KB Correct.
2 Correct 119 ms 9996 KB Correct.
3 Correct 107 ms 10440 KB Correct.
4 Correct 110 ms 9972 KB Correct.
5 Correct 63 ms 5464 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 9820 KB Correct.
2 Correct 20 ms 9856 KB Correct.
3 Correct 20 ms 9820 KB Correct.
4 Correct 21 ms 16732 KB Correct.
5 Correct 21 ms 5468 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 9820 KB Correct.
2 Correct 17 ms 9884 KB Correct.
3 Correct 31 ms 8532 KB Correct.
4 Correct 14 ms 12380 KB Correct.
5 Correct 18 ms 5468 KB Correct.
6 Correct 19 ms 9820 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 10348 KB Correct.
2 Correct 21 ms 10264 KB Correct.
3 Correct 498 ms 96596 KB Correct.
4 Correct 244 ms 27692 KB Correct.
5 Correct 532 ms 52528 KB Correct.
6 Correct 207 ms 30172 KB Correct.
7 Correct 242 ms 29868 KB Correct.
8 Correct 201 ms 12004 KB Correct.
9 Correct 101 ms 10104 KB Correct.
10 Correct 91 ms 10084 KB Correct.
11 Correct 170 ms 9904 KB Correct.
12 Correct 116 ms 10112 KB Correct.
13 Correct 124 ms 10072 KB Correct.
14 Correct 240 ms 52524 KB Correct.
15 Correct 217 ms 18852 KB Correct.
16 Correct 112 ms 10088 KB Correct.
17 Correct 134 ms 10080 KB Correct.
18 Correct 118 ms 10332 KB Correct.
19 Correct 294 ms 10040 KB Correct.
20 Correct 7 ms 5468 KB Correct.
21 Correct 9 ms 5724 KB Correct.
22 Correct 17 ms 10748 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 10284 KB Correct.
2 Correct 45 ms 10544 KB Correct.
3 Correct 782 ms 100180 KB Correct.
4 Correct 279 ms 14712 KB Correct.
5 Correct 1183 ms 77404 KB Correct.
6 Correct 494 ms 37388 KB Correct.
7 Correct 418 ms 41512 KB Correct.
8 Correct 242 ms 10060 KB Correct.
9 Correct 207 ms 10440 KB Correct.
10 Correct 188 ms 10320 KB Correct.
11 Correct 248 ms 5768 KB Correct.
12 Correct 244 ms 11376 KB Correct.
13 Correct 254 ms 11260 KB Correct.
14 Correct 955 ms 47720 KB Correct.
15 Correct 813 ms 56640 KB Correct.
16 Correct 419 ms 25448 KB Correct.
17 Correct 268 ms 14164 KB Correct.
18 Correct 224 ms 11220 KB Correct.
19 Correct 278 ms 11524 KB Correct.
20 Correct 257 ms 11348 KB Correct.
21 Correct 658 ms 12880 KB Correct.
22 Correct 14 ms 5500 KB Correct.
23 Correct 18 ms 5980 KB Correct.
24 Correct 32 ms 11512 KB Correct.