Submission #1197527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197527		b00legen	Cyberland (APIO23_cyberland)	C++17	44 / 100	3096 ms	2162688 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

double solve(int n, int m, int k, int h, vector<int>x, vector<int>y, vector<int>c, vector<int>arr) {
	vector<pair<int, double> >g[n];
	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]});
	}
	vector<int>bg;
	{
		int vis[n];
		vis[1] = 2;
		for (int i = 1; i < n; i++)
		vis[i] = 0;
		queue<int>q;
		q.push(0);
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			if (arr[v] == 0 || v == 0) {
				bg.push_back(v);
				vis[v] = 2;
			}
			for (size_t i = 0; i < g[v].size(); i++) {
				int to = g[v][i].first;
				if (to != h && !vis[to]) {
					q.push(to);
					vis[to] = 1;
				}
			}
		}
		vis[h] = 1;
		
		vector<pair<int, double> >g2[n];
		for (int v = 0; v < n; v++) {
			if (!vis[v])
			continue;
			for (size_t i = 0; i < g[v].size(); i++) {
				int to = g[v][i].first;
				if (vis[to] == 1)
				g2[v].push_back(g[v][i]);
			}
		}
		for (int i = 0; i < n; i++)
		g[i] = g2[i];
	}
	pair<double, int>d[n];
	for (int i = 0; i < n; i++)
	d[i] = {1e15, 0};
	queue<pair<pair<double, int>, int>>q;
	for (size_t i = 0; i < bg.size(); i++)
	q.push({{0, k}, bg[i]});
	while (!q.empty()) {
		pair<double, int>vl = q.front().first;
		int v = q.front().second;
		q.pop();
		if (vl.first < d[v].first || vl.second > d[v].second) {
			d[v] = vl;
			for (size_t i = 0; i < g[v].size(); i++) {
				int to = g[v][i].first;
				q.push({{vl.first + g[v][i].second, vl.second}, to});
				if (arr[to] == 2 && vl.second)
				q.push({{(vl.first + g[v][i].second) / 2, vl.second - 1}, to});
			}
		}
	}
	if (d[h].first == 1e15)
	return -1;
	else
	return d[h].first;
}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3