QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#811663 | #5683. 大富翁 | thupc_team# | WA | 0ms | 3552kb | C++14 | 1.8kb | 2024-12-12 22:40:34 | 2024-12-12 22:40:35 |
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]) if(v != f){
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::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++){
if(a[i] == 0) ans -= v[i];
else ans += v[i];
}
std::vector<int> pre(N);
std::function<void(int, int)> dfs1 = [&](int u, int f){
if(u != 0){
if(a[u] == 0){
ans -= pre[f];
} else{
ans += deep[u] - pre[f];
}
pre[u] = pre[f];
}
pre[u] += a[u];
for(int v : adj[u]) if(v != f){
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 因你今晚共我唱
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
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: -100
Wrong Answer
time: 0ms
memory: 3552kb
input:
10 1 0 0 0 0 0 0 0 0 1 8 1 9 10 9 8 4 5 1
output:
3
result:
wrong answer 1st lines differ - expected: '2', found: '3'