QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#878336#9696. Analysisucup-team3802#WA 1ms3584kbC++231.6kb2025-02-01 14:50:002025-02-01 14:50:00

Judging History

This is the latest submission verdict.

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

answer

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

#define rep(i, l, r) for(ll i = l; i < r; i++)
#define all(ar) begin(ar), end(ar)

void chmin(ll &a, ll b) { a = min(a, b); }

void solve() {
    ll n, a, b;
    cin >> n >> a >> b;
    vector<vector<int>> g(n);
    rep(i, 0, n - 1) {
        ll u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    auto dfs = [&](auto self, ll v, ll p) -> pair<ll, ll> {
        vector<pair<ll, ll>> ch;
        for(int u : g[v]) {
            if(u != p) {
                ch.push_back(self(self, u, v));
            }
        }

        if(ch.empty()) return {0, 0};
        for(auto &[f, s] : ch) {
            s += a;
        }

        sort(all(ch), [&](pair<ll, ll> p1, pair<ll, ll> p2) {
            return p1.second - p1.first < p2.second - p2.first;
        });

        vector<ll> res(2, 1LL << 60);

        ll s1 = 0;
        for(auto [f, s] : ch) s1 += f;
        res[(ch.size() + 1) % 2] = s1 + (ch.size() / 2) * b;
        rep(i, 0, ch.size()) {
            s1 -= ch[i].first;
            s1 += ch[i].second;
            chmin(res[(ch.size() - i) % 2], s1 + ((ch.size() - i - 1) / 2) * b);
        }
        // cout << v + 1 << " " << res[0] << " " << res[1] << endl;
        return {res[0], res[1]};
    };

    int r = 0;
    while(g[r].size() > 1) r++;

    auto [f, s] = dfs(dfs, r, -1);
    cout << f << endl;
}

int main() {
    int t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

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

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:

243437982

result:

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