QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#236099#6438. Crystalflyucup-team1001#RE 0ms3620kbC++171.7kb2023-11-03 16:24:262023-11-03 16:24:26

Judging History

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

  • [2023-11-03 16:24:26]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3620kb
  • [2023-11-03 16:24:26]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ull = unsigned long long;

#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define endl "\n"
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define lowbit(x) x&(-x)

void solve() {
    int n;
    cin >> n;
    vector<ll> ans(n + 1);
    vector<ll> dp(n + 1);
    vector<int> time(n + 1);
    vector<vector<int>> mp(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> ans[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> time[i];
    }
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        mp[x].emplace_back(y);
        mp[y].emplace_back(x);
    }
    function<void(int, int)> dfs = [&](int len, int f) {
        multiset<int> s;
        for (auto i: mp[len]) {
            if (i == f)continue;
            s.insert(ans[i]);
            dfs(i, len);
        }
        ll maxs = ans[len];
        for (auto i: mp[len]) {
            if (i == f)continue;
            if (time[i] < 3) {
                maxs = max(maxs, ans[len] + dp[i] - ans[i] + *(--s.end()));
            } else {
                int t = ans[i];
                auto it = s.find(t);
                s.erase(it);
                maxs = max(maxs, ans[len] + dp[i] + *(--s.end()));
                s.insert(t);
            }
        }
        dp[len] = maxs;
    };
    dfs(1, -1);
    cout << dp[1] << endl;
}
//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


int main() {
    IOS
    int t;
    cin >> t;
    while (t--)solve();
}

详细

Test #1:

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

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
Runtime Error

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:


result: