QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#811748 | #5683. 大富翁 | thupc_team | TL | 0ms | 3852kb | C++20 | 2.0kb | 2024-12-13 00:24:11 | 2024-12-13 00:24:12 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using pii = std::pair<int, int>;
#define all(a) a.begin(), a.end()
#define chmin(a, b) a = std::min(a, (b));
#define chmax(a, b) a = std::max(a, (b));
void solve(){
int N;
std::cin >> N;
std::vector<int> v(N);
for(int i = 0; i < N; i++){
std::cin >> v[i];
}
std::vector<std::vector<int> > adj(N);
for(int i = 1; i < N; i++){
int f;
std::cin >> f;
--f;
adj[f].push_back(i);
}
std::vector<int> deep(N), sz(N);
std::function<void(int, int)> dfs = [&](int u, int f){
deep[u] = u == 0 ? 0 : deep[f] + 1;
sz[u] = 1;
for(int v : adj[u]){
dfs(v, u);
sz[u] += sz[v];
}
};
dfs(0, -1);
std::vector<int> id(N);
for(int i = 0; i < N; i++){
id[i] = i;
}
auto val = [&](int i){
return -deep[i] + sz[i] - v[i];
};
std::sort(all(id), [&](int i, int j){
return val(i) >= val(j);
});
// std::swap(id[6], id[7]);
std::vector<int> a(N);
for(int i = 1; i < N; i += 2){
a[id[i]] = 1;
}
i64 ans = 0;
for(int i = 0; i < N; i++){
// std::cerr << id[i] + 1 << "\n";
// std::cerr << val(i) << "\n";
if(a[i] == 0) ans -= v[i];
// else ans += v[i];
}
// std::cerr << ans << "\n";
std::vector<int> pre(N);
std::function<void(int, int)> dfs1 = [&](int u, int f){
if(u != 0){
// std::cerr << u + 1 << " ";
if(a[u] == 0){
ans -= pre[f];
// std::cerr << -pre[f] << "\n";
} else{
ans += deep[u] - pre[f];
// std::cerr << deep[u] - pre[f] << "\n";
}
pre[u] = pre[f];
}
pre[u] += a[u];
for(int v : adj[u]){
dfs1(v, u);
}
};
dfs1(0, -1);
std::cout << ans << "\n";
}
int main(){
std::cin.tie(0);
std::ios::sync_with_stdio(0);
int T = 1;
// std::cin >> T;
for(int i = 0; i < T; i++){
solve();
}
return 0;
}
/*
来日纵使千千阕歌,飘于远方我路上
来日纵使千千晚星,亮过今晚月亮
都比不起这宵美丽,亦绝不可使我更欣赏
Ah 因你今晚共我唱
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
input:
8 0 1 1 0 0 0 0 0 3 1 8 4 1 3 1
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
10 1 0 0 0 0 0 0 0 0 1 8 1 9 10 9 8 4 5 1
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
8 1 0 1 0 0 1 0 0 1 6 2 1 2 1 5
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
8 0 0 0 1 1 0 1 1 7 1 3 4 1 4 3
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
10 0 0 1 0 0 0 0 1 1 0 1 5 1 1 9 1 2 4 4
output:
3
result:
ok single line: '3'
Test #6:
score: -100
Time Limit Exceeded
input:
199998 2 2 3 2 1 3 0 2 0 3 2 0 2 2 1 1 3 3 3 3 2 0 1 2 0 3 1 1 0 0 3 3 3 3 0 3 2 2 1 1 2 2 0 3 3 3 1 2 0 2 2 1 2 0 3 2 0 0 0 3 2 3 0 1 1 2 0 2 2 0 3 1 1 2 3 1 0 3 0 2 1 0 3 3 1 1 2 3 1 0 3 0 1 2 3 1 3 3 0 3 1 2 1 1 3 2 1 3 3 3 1 1 2 3 2 0 2 3 2 2 1 1 2 1 2 0 1 0 1 3 3 2 3 2 0 3 2 2 2 0 3 2 1 2 3 1 2...