제출 #982083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982083		vjudge1	Cyberland (APIO23_cyberland)	C++17	49 / 100	38 ms	13916 KiB

cyberland

#include "cyberland.h"

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

using ll  = long long;
using pll = pair<ll, ll>;

double solveNoTwos(int N, int M, int K, int H, vector<vector<pll>> G,
                   vector<int> arr) {
	vector<bool> v(N);
	priority_queue<pair<double, ll>, vector<pair<double, ll>>,
	               greater<pair<double, ll>>>
	  q;
	arr[0] = 0;

	{
		vector<bool> v(N);
		queue<ll>    qt;
		qt.push(0);
		while (qt.size()) {
			ll node = qt.front();
			qt.pop();
			if (v[node] || node == H) continue;
			v[node] = true;
			if (!arr[node]) q.push({0, node});
			for (pll& nei : G[node]) qt.push(nei.first);
		}
	}

	double ans = LLONG_MAX;
	while (q.size()) {
		ll     node = q.top().second;
		double c    = q.top().first;
		q.pop();
		if (node == H) ans = min(ans, c);
		if (v[node] || node == H) continue;
		v[node] = true;
		for (pll& nei : G[node]) q.push({nei.second + c, nei.first});
	}

	if (ans == LLONG_MAX) return -1;
	return ans;
}

double solve3(int N, int M, int K, int H, vector<vector<pll>> G,
              vector<int> arr) {
	double                            ans = LLONG_MAX;
	queue<pair<pair<ll, ll>, double>> q;
	vector<bool>                      v(N);
	q.push({{0, -1}, 0});

	while (q.size()) {
		ll     node = q.front().first.first;
		ll     p    = q.front().first.second;
		double c    = q.front().second;
		q.pop();

		if (arr[node] == 2) c /= 2;
		if (arr[node] == 0) c = 0;

		if (node == H) ans = min(ans, c);
		if (v[node] || node == H) continue;
		v[node] = true;

		for (pll& nei : G[node])
			if (nei.first != p && !v[nei.first])
				q.push({{nei.first, node}, nei.second + c});
	}

	if (ans == LLONG_MAX) return -1;
	return ans;
}

double solveChain(int N, int K, int H, vector<int>& c,
                  vector<int> arr) {
	set<ll> divs;
	for (int i = H; i && divs.size() < K; i--)
		if (arr[i] == 2) divs.insert(i);

	double ans = 0;
	for (int i = 0; i <= H; i++)
		if (arr[i] == 0) ans = 0;
		else if (arr[i] == 2 && divs.count(i))
			ans /= 2;
		else
			ans += c[i];

	return ans;
}

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) {
	vector<vector<pll>> 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]});
	}
	if (arr[H] == 0) return 0;
	if (N == 2 || (G[0].size() == 1 && G[0][0].first == H)) {
		if (!M) return -1;
		if (arr[H] == 2) return G[0][0].second / double(2);
		return G[0][0].second;
	}
	if (N == 3) return solve3(N, M, K, H, G, arr);

	bool NoTwos = 1;
	for (int& i : arr)
		if (i == 2) {
			NoTwos = 0;
			break;
		}

	if (NoTwos) return solveNoTwos(N, M, K, H, G, arr);
	return solveChain(N, K, H, c, arr);
}

컴파일 시 표준 에러 (stderr) 메시지

cyberland.cpp: In function 'double solveChain(int, int, int, std::vector<int>&, std::vector<int>)':
cyberland.cpp:78:35: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |  for (int i = H; i && divs.size() < K; i--)
      |                       ~~~~~~~~~~~~^~~

• 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: 0 / 29
• Subtask 8: 0 / 3