QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#811748#5683. 大富翁thupc_teamTL 0ms3852kbC++202.0kb2024-12-13 00:24:112024-12-13 00:24:12

Judging History

This is the latest submission verdict.

  • [2024-12-13 00:24:12]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 3852kb
  • [2024-12-13 00:24:11]
  • 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]){
			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...

output:


result: