oj.uz

답안 #756863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
756863 2023-06-12T10:38:29 Z DarkMatter 사이버랜드 (APIO23_cyberland) C++17
78 / 100
 832 ms 18992 KB 
#define _CRT_SECURE_NO_WARNINGS
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int>pi;
typedef pair<ll, ll>pl;
typedef vector<pi>vpi;
typedef vector<pl>vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<bool> vb;
const long double PI = acos(-1);
const ll oo = 2e18 + 10;
const int MOD = 1e9 + 7;
const ll N = 2e5 + 10;
#define endl '\n'
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define read(v) for (auto& it : v) scanf("%d", &it);
#define readL(v) for (auto& it : v) scanf("%lld", &it);
#define print(v) for (auto it : v) printf("%d ", it); puts("");
#define printL(v) for (auto it : v) printf("%lld ", it); puts("");
#include <vector>
vpl graph[N];
double cost[N], copCost[N], ret = double(oo);
int n, m, k, h;
bool vis[N];
vi vec;
void reset() {
	for (int i = 0; i <= n; i++)
		vis[i] = false, graph[i].clear();
}
void DFS1(int u) {
	vis[u] = true;
	for (auto& v : graph[u]) {
		if (vis[v.first])
			continue;
		DFS1(v.first);
	}
}
void DFS2(int u) {
	vis[u] = true;
	vec.push_back(u);
	for (auto& v : graph[u]) {
		if (v.first == h || vis[v.first])
			continue;
		DFS2(v.first);
	}
}
void Dijkstra() {
	priority_queue<pair<double, int>>pq;
	for (int i = 0; i < n; i++)
		pq.push({ -cost[i],i });
	while (!pq.empty()) {
		pair<double, int>cur = pq.top();
		pq.pop();
		if (cur.second != h && -cur.first == cost[cur.second]) {
			for (auto& it : graph[cur.second]) {
				double sum = cost[cur.second] + it.second;
				if (sum < cost[it.first]) {
					cost[it.first] = sum, pq.push({ -cost[it.first],it.first });
				}
			}
		}
	}
}
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) {
	n = N, m = M, k = min(K, 70), h = H;
	reset();
	for (int i = 0; i < m; i++)
		graph[x[i]].push_back({ y[i],c[i] }), graph[y[i]].push_back({ x[i],c[i] });
	DFS1(0);
	if (!vis[h])
		return -1;
	for (int i = 0; i <= n; i++)
		cost[i] = oo, vis[i] = false;
	vec.clear();
	DFS2(0);
	for (auto& it : vec)
		if (!arr[it] || !it)
			cost[it] = 0;
	ret = double(oo);
	for (int i = 0; i <= k; i++) {
		Dijkstra();
		ret = min(ret, cost[h]), cost[h] = oo;
		for (int j = 0; j < n; j++)
			copCost[j] = cost[j];
		for (int j = 0; j < n; j++) {
			if (arr[j] != 2)
				continue;
			double mn = oo;
			for (auto& it : graph[j]) {
				double sum = copCost[it.first] + it.second;
				mn = min(mn, sum);
			}
			mn /= double(2);
			cost[j] = min(cost[j], mn);
		}
	}
	return ret;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 5076 KB Correct.
2 Correct 42 ms 5180 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 5204 KB Correct.
2 Correct 169 ms 5196 KB Correct.
3 Correct 149 ms 5204 KB Correct.
4 Correct 158 ms 5204 KB Correct.
5 Correct 188 ms 5256 KB Correct.
6 Correct 194 ms 6584 KB Correct.
7 Correct 266 ms 6668 KB Correct.
8 Correct 133 ms 7844 KB Correct.
9 Correct 105 ms 5076 KB Correct.
10 Correct 98 ms 5076 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 5176 KB Correct.
2 Correct 156 ms 5160 KB Correct.
3 Correct 144 ms 5176 KB Correct.
4 Correct 117 ms 5080 KB Correct.
5 Correct 106 ms 5076 KB Correct.
6 Correct 42 ms 6100 KB Correct.

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 663 ms 13652 KB Correct.
2 Incorrect 229 ms 5308 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 5416 KB Correct.
2 Correct 85 ms 5396 KB Correct.
3 Correct 81 ms 5344 KB Correct.
4 Correct 133 ms 6740 KB Correct.
5 Correct 51 ms 5076 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 5348 KB Correct.
2 Correct 65 ms 5336 KB Correct.
3 Correct 46 ms 11596 KB Correct.
4 Correct 67 ms 6448 KB Correct.
5 Correct 58 ms 5080 KB Correct.
6 Correct 76 ms 5364 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 5296 KB Correct.
2 Correct 15 ms 5312 KB Correct.
3 Correct 832 ms 18992 KB Correct.
4 Correct 461 ms 8608 KB Correct.
5 Correct 351 ms 14728 KB Correct.
6 Correct 120 ms 11848 KB Correct.
7 Correct 413 ms 8560 KB Correct.
8 Correct 320 ms 5680 KB Correct.
9 Correct 76 ms 5272 KB Correct.
10 Correct 76 ms 5324 KB Correct.
11 Correct 286 ms 5524 KB Correct.
12 Correct 100 ms 5324 KB Correct.
13 Correct 85 ms 5372 KB Correct.
14 Correct 406 ms 12276 KB Correct.
15 Correct 359 ms 7036 KB Correct.
16 Correct 85 ms 5364 KB Correct.
17 Correct 109 ms 5324 KB Correct.
18 Correct 91 ms 5324 KB Correct.
19 Correct 296 ms 5368 KB Correct.
20 Correct 8 ms 4948 KB Correct.
21 Correct 8 ms 5076 KB Correct.
22 Correct 11 ms 5744 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 186 ms 5292 KB Wrong Answer.
2 Halted 0 ms 0 KB -