QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#879602#9696. Analysisucup-team3695WA 0ms12000kbC++201.9kb2025-02-02 07:24:382025-02-02 07:24:38

Judging History

This is the latest submission verdict.

  • [2025-02-06 00:45:32]
  • hack成功,自动添加数据
  • (/hack/1517)
  • [2025-02-02 07:24:38]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 12000kb
  • [2025-02-02 07:24:38]
  • Submitted

answer

#include <bits/extc++.h>

using namespace std;
namespace rg = ranges;

constexpr int N = 1000000;

alignas(64) int I[N + 1], G[2 * N - 2], S[N - 1];
alignas(64) pair<int, int> E[N - 1];
alignas(64) pair<long long, long long> F[N];

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	int		  n;
	long long A, B;
	cin >> n >> A >> B;
	for (int i = 0; i < n - 1; i++)
	{
		auto &[u, v] = E[i];
		cin >> u >> v;
		u--;
		v--;
		I[u]++;
		I[v]++;
	}
	if (n <= 2)
	{
		cout << "0";
		return 0;
	}
	int r = 0;
	while (I[r] == 1)
		r++;
	for (int i = 0; i < n; i++)
		I[i + 1] += I[i];
	for (int i = 0; i < n - 1; i++)
	{
		auto [u, v] = E[i];
		G[--I[u]]	= v;
		G[--I[v]]	= u;
	}

	constexpr auto diff = [](int i)
	{
		return F[i].first - F[i].second;
	};
	constexpr auto rpar = [](int u, int v)
	{
		for (int i = I[v]; i < I[v + 1] - 1; i++)
			if (G[i] == u)
			{
				G[i] = G[I[v + 1] - 1];
				break;
			}
	};

	int ss = 0;
	for (int i = I[r]; i < I[r + 1]; i++)
	{
		int v	= G[i];
		S[ss++] = v;
		rpar(r, v);
	}
	while (ss)
	{
		int v = S[--ss];
		if (v >= 0)
		{
			S[ss++] = v | INT_MIN;
			for (int i = I[v]; i < I[v + 1] - 1; i++)
			{
				int w	= G[i];
				S[ss++] = w;
				rpar(v, w);
			}
		}
		else
		{
			v &= INT_MAX;
			rg::sort(G + I[v], G + I[v + 1] - 1, {}, diff);
			long long sum = 0;
			for (int i = I[v]; i < I[v + 1] - 1; i++)
				sum += F[G[i]].second;
			F[v] = {sum, sum};
			for (int i = I[v]; i < I[v + 1] - 1; i++)
			{
				int k = i - I[v] + 1;
				sum += diff(G[i]);
				F[v].first	= min(F[v].first, sum + k / 2 * B);
				F[v].second = min(F[v].second, sum + (k + 1) / 2 * B);
			}
			F[v].second += min(A, B);
		}
	}

	long long sum = 0;
	for (int i = I[r]; i < I[r + 1]; i++)
		sum += F[G[i]].second;
	long long res = sum;
	for (int i = I[r]; i < I[r + 1]; i++)
	{
		sum += diff(G[i]);
		res = min(res, sum + (i - I[r]) / 2 * B);
	}
	cout << res;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 11780kb

input:

5 100 1000
1 2
2 3
3 4
4 5

output:

0

result:

ok 1 number(s): "0"

Test #2:

score: 0
Accepted
time: 0ms
memory: 11872kb

input:

5 100 200
1 2
1 3
2 4
2 5

output:

100

result:

ok 1 number(s): "100"

Test #3:

score: 0
Accepted
time: 0ms
memory: 11992kb

input:

10 133494816 109943166
10 8
5 3
1 2
8 9
8 5
2 4
8 7
8 6
10 1

output:

219886332

result:

ok 1 number(s): "219886332"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 12000kb

input:

10 165074331 854297934
6 2
2 7
9 8
2 9
9 10
6 3
6 4
5 6
6 1

output:

990445986

result:

wrong answer 1st numbers differ - expected: '825371655', found: '990445986'