Submission #756863

#	Time	Username	Problem	Language	Result	Execution time	Memory
756863		DarkMatter	Cyberland (APIO23_cyberland)	C++17	78 / 100	832 ms	18992 KiB

cyberland

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 0 / 3