QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#811663#5683. 大富翁thupc_team#WA 0ms3552kbC++141.8kb2024-12-12 22:40:342024-12-12 22:40:35

Judging History

This is the latest submission verdict.

  • [2024-12-12 22:40:35]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3552kb
  • [2024-12-12 22:40:34]
  • Submitted

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 因你今晚共我唱
*/

详细

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'