QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#881238#9696. AnalysisLEFt_bankWA 0ms3712kbC++201.7kb2025-02-04 14:00:222025-02-04 14:00:22

Judging History

This is the latest submission verdict.

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

answer

#pragma GCC optimize(3, "Ofast", "unroll-loops", "-funroll-loops")
#include<bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
using i128 = __int128;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = unsigned __int128;

main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  i32 n;
  i64 A, B;
  cin >> n >> A >> B;
  vector<vector<i32>> ed(n + 1);
  for (i32 _ = 1; _ < n; _++) {
    i32 u, v;
    cin >> u >> v;
    ed[u].emplace_back(v);
    ed[v].emplace_back(u);
  }

  vector<i32> dep(n + 1), son(n + 1), mson(n + 1);
  i32 rt = -1, md = -1;

  auto dfs = [&](auto &&self, i32 u, i32 fa) -> void {
    dep[u] = dep[fa] + 1;
    if (dep[u] > md) {
      rt = u;
      md = dep[u];
    }
    mson[u] = dep[u];
    for (i32 v : ed[u]) {
      if (v != fa) {
        self(self, v, u);
        if (mson[v] > mson[u]) {
          son[u] = v;
          mson[u] = mson[v];
        }
      }
    }
  };

  dfs(dfs, 1, 1);
  fill(son.begin(), son.end(), 0);
  dep[rt] = 0;
  i32 t = rt;
  dfs(dfs, rt, rt);
  vector<i64> len;
  
//	for (i32 i = 1; i <= n; i++) {
//		cout << son[i] << ' ';
//	}
//	cout << '\n';

  auto tdfs = [&](auto &&self, i32 u, i32 fa, i32 tp) -> void {
  	if (tp == u) {
			len.emplace_back(mson[u] - dep[u] + 1);
		}
    if (son[u]) {
      self(self, son[u], u, tp);
    }
    for (i32 v : ed[u]) {
    	if (v != son[u] && v != fa) {
    		self(self, v, u, v);
			}
		}
  };

//	return 0;
	tdfs(tdfs, t, t, t);
	sort(len.begin(), len.end());
	len.pop_back();
	i64 ans = 0;
	for (auto i : len) {
		ans += min(B, i * A);
	}
	cout << ans << '\n';

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3712kb

input:

5 100 200
1 2
1 3
2 4
2 5

output:

100

result:

ok 1 number(s): "100"

Test #3:

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

input:

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

output:

329829498

result:

wrong answer 1st numbers differ - expected: '219886332', found: '329829498'