oj.uz

답안 #1050889

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1050889 2024-08-09T16:18:35 Z vjudge1 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 262 ms 169668 KB 
#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ar array
const int N = 2e5 + 20;

namespace DSU{
	int p[N];
	void init(int n){
		iota(p, p + n + 1, 0);
	}
	int find(int x){
		if(p[x] == x)return x;
		return p[x] = find(p[x]);
	}
	bool join(int u,int v){
		u = find(u), v = find(v);
		if(u == v)return 0;
		p[u] = v;
		return 1;
	}
};
ld dist[N][100];
priority_queue<pair<ld, ar<int, 2> >, vector<pair<ld, ar<int, 2>>>, greater<pair<ld, ar<int, 2>>>> pq;

void push(int k,int x, ld d){
	if(dist[x][k] > d){
		dist[x][k] = d;
		pq.push({d, {x, k}});
	}
}

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> A) {
	vector<ar<int, 2>> g[n];;
	K = min(K, 69);
	DSU::init(n);
	for(int i = 0;i < m;i++){
		if(x[i] != h && y[i] != h)DSU::join(x[i], y[i]);
		g[x[i]].push_back({y[i], c[i]});
		g[y[i]].push_back({x[i], c[i]});
	}
	ld pow[K + 1];
	pow[0] = 1;
	for(int i = 1;i <= K;i++)pow[i] = pow[i - 1] / 2;
	A[0] = 0;
	pq = priority_queue<pair<ld, ar<int, 2> >, vector<pair<ld, ar<int, 2>>>, greater<pair<ld, ar<int, 2>>>>();
	for(int i = 0;i < n;i++){
		for(int j = 0;j <= K;j++){
			dist[i][j] = 1e18;
		}
	}
	push(K, h, 0);
	while(pq.size()){
		ld d = pq.top().first;
		auto [x, k] = pq.top().second;
		pq.pop();
		if(dist[x][k] < d)continue;
		if(A[x] == 0)return d;
		for(auto [u, c]: g[x]){
			if(DSU::find(u) != DSU::find(0))continue;
			push(k, u, d + c * pow[K - k]);
			if(A[x] == 2 && k > 0)push(k - 1, u, d + c * pow[K - k + 1]);
		}
	}
    return -1;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 604 KB Correct.
2 Correct 13 ms 836 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 2652 KB Correct.
2 Correct 21 ms 2652 KB Correct.
3 Correct 20 ms 2652 KB Correct.
4 Correct 26 ms 2804 KB Correct.
5 Correct 21 ms 2652 KB Correct.
6 Correct 20 ms 17752 KB Correct.
7 Correct 22 ms 17756 KB Correct.
8 Correct 11 ms 33116 KB Correct.
9 Correct 19 ms 604 KB Correct.
10 Correct 19 ms 604 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 2652 KB Correct.
2 Correct 20 ms 3676 KB Correct.
3 Correct 18 ms 3724 KB Correct.
4 Correct 20 ms 1548 KB Correct.
5 Correct 19 ms 1404 KB Correct.
6 Correct 5 ms 15708 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 97372 KB Correct.
2 Correct 26 ms 3672 KB Correct.
3 Correct 21 ms 3704 KB Correct.
4 Correct 19 ms 3672 KB Correct.
5 Correct 23 ms 1420 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 2904 KB Correct.
2 Correct 23 ms 2652 KB Correct.
3 Correct 22 ms 2828 KB Correct.
4 Correct 21 ms 18180 KB Correct.
5 Correct 19 ms 604 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 2800 KB Correct.
2 Correct 18 ms 3676 KB Correct.
3 Correct 57 ms 127708 KB Correct.
4 Correct 15 ms 14168 KB Correct.
5 Correct 27 ms 1372 KB Correct.
6 Correct 22 ms 3676 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 2800 KB Correct.
2 Correct 3 ms 4956 KB Correct.
3 Correct 62 ms 160496 KB Correct.
4 Correct 35 ms 39764 KB Correct.
5 Correct 34 ms 65360 KB Correct.
6 Correct 19 ms 22608 KB Correct.
7 Correct 39 ms 43856 KB Correct.
8 Correct 36 ms 9036 KB Correct.
9 Correct 20 ms 3676 KB Correct.
10 Correct 19 ms 3676 KB Correct.
11 Correct 37 ms 4684 KB Correct.
12 Correct 22 ms 3676 KB Correct.
13 Correct 20 ms 3808 KB Correct.
14 Correct 41 ms 78628 KB Correct.
15 Correct 33 ms 24312 KB Correct.
16 Correct 21 ms 3928 KB Correct.
17 Correct 22 ms 3712 KB Correct.
18 Correct 21 ms 3672 KB Correct.
19 Correct 40 ms 4676 KB Correct.
20 Correct 3 ms 600 KB Correct.
21 Correct 3 ms 2652 KB Correct.
22 Correct 2 ms 3164 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2856 KB Correct.
2 Correct 4 ms 4952 KB Correct.
3 Correct 116 ms 169668 KB Correct.
4 Correct 36 ms 13404 KB Correct.
5 Correct 38 ms 65364 KB Correct.
6 Correct 20 ms 22620 KB Correct.
7 Correct 49 ms 61672 KB Correct.
8 Correct 44 ms 4944 KB Correct.
9 Correct 28 ms 3804 KB Correct.
10 Correct 28 ms 3600 KB Correct.
11 Correct 262 ms 1876 KB Correct.
12 Correct 32 ms 3676 KB Correct.
13 Correct 30 ms 3860 KB Correct.
14 Correct 50 ms 66324 KB Correct.
15 Correct 58 ms 84048 KB Correct.
16 Correct 39 ms 32904 KB Correct.
17 Correct 39 ms 9044 KB Correct.
18 Correct 33 ms 3904 KB Correct.
19 Correct 31 ms 3916 KB Correct.
20 Correct 31 ms 3856 KB Correct.
21 Correct 58 ms 4688 KB Correct.
22 Correct 4 ms 604 KB Correct.
23 Correct 4 ms 2768 KB Correct.
24 Correct 2 ms 3164 KB Correct.