QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#811695#5683. 大富翁thupc_team#WA 1ms3848kbC++142.0kb2024-12-12 23:17:592024-12-12 23:18:01

Judging History

This is the latest submission verdict.

  • [2024-12-12 23:18:01]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3848kb
  • [2024-12-12 23:17:59]
  • 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] * 2;
	};
	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: 0
Wrong Answer
time: 1ms
memory: 3848kb

input:

8
0 1 1 0 0 0 0 0
3 1 8 4 1 3 1

output:

4

result:

wrong answer 1st lines differ - expected: '3', found: '4'