QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#692498#6438. CrystalflyRegistrationError#WA 0ms3780kbC++201.7kb2024-10-31 14:37:342024-10-31 14:38:03

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 14:38:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3780kb
  • [2024-10-31 14:37:34]
  • 提交

answer

#include <bits/stdc++.h>
#define all(a) begin(a), end(a)
#define sz(a) (int) (a).size()
#define int long long
using namespace std;

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    vector<int> t(n + 1);
    vector<vector<int> > edg(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> t[i];
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        edg[u].push_back(v);
        edg[v].push_back(u);
    }
    vector<int> dp(n + 1, 0);
    vector<int> dpSum(n + 1, 0);
    priority_queue<pair<int, int> > pq;
    auto dfs = [&](auto &&dfs, int id, int par) -> void {
        while (!pq.empty()) pq.pop();
        int maxx = 0, maxi = 0;
        // cout << id << endl; cout.flush();
        for (auto i : edg[id]) {
            if (i == par) continue;
            dfs(dfs, i, id);
            dpSum[id] += dp[i];
            if (a[i] > maxx) {
                maxx = a[i];
                maxi = i;
            }
            pq.push({dpSum[i] - dp[i] + a[i], i});
        }
        dp[id] = dpSum[id] + maxx;
        for (auto i : edg[id]) {
            if (i == par) continue;
            if (t[i] == 3) {
                pair<int, int> tp = pq.top();
                if (tp.second == i) {
                    pair<int, int> tmp = tp;
                    pq.pop();
                    tp = pq.top();
                    pq.push(tmp);
                }
                dp[id] = max(dp[id], dpSum[id] + a[i] + tp.first);
            }
        }
    };
    dfs(dfs, 1, -1);
    cout << dp[1] + a[1] << "\n";
}

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

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

詳細信息

Test #1:

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

input:

2
5
1 10 100 1000 10000
1 2 1 1 1
1 2
1 3
2 4
2 5
5
1 10 100 1000 10000
1 3 1 1 1
1 2
1 3
2 4
2 5

output:

10101
10111

result:

ok 2 number(s): "10101 10111"

Test #2:

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

input:

10
6
8 1 1 5 8 9
2 1 2 2 2 2
1 2
2 3
2 4
1 5
2 6
6
6 4 4 1 3 6
2 1 3 3 3 3
1 2
1 3
3 4
4 5
5 6
6
10 5 1 8 5 1
1 3 1 2 2 2
1 2
2 3
2 4
2 5
3 6
10
6 8 8 9 6 9 5 6 6 4
2 1 3 3 2 2 2 2 3 1
1 2
1 3
3 4
4 5
5 6
4 7
2 8
7 9
9 10
7
10 9 1 5 7 5 4
1 1 1 2 1 3 2
1 2
1 3
3 4
3 5
5 6
1 7
5
7 1 1 4 2
3 1 3 2 2
1...

output:

25
44
29
66
36
18
17
23
19
18

result:

wrong answer 2nd numbers differ - expected: '24', found: '44'