QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562253#9261. Toll RoadBaneist#WA 0ms13020kbC++141.1kb2024-09-13 16:07:322024-09-13 16:07:36

Judging History

你现在查看的是最新测评结果

  • [2024-09-13 16:07:36]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:13020kb
  • [2024-09-13 16:07:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;


typedef long long ll;
const int MAXN = 300005;

vector<int> graph[MAXN];
int n;

int fa[MAXN];
ll sz[MAXN];

int Fa(int x) {
	return fa[x] == x ? x : fa[x] = Fa(fa[x]);
}


void solve()
{
	ll ans = 0;
	cin >>n;
	for (int i=2, u; i<=n; i++) {
		cin >>u;
		graph[u].push_back(i);
		graph[i].push_back(u);
	}


	for (int i=1; i<=n; i++) {
		fa[i] = i;
		sz[i] = 1;
	}
	for (int u=n; u>=1; u--) {
		for (int v: graph[u]) if (v > u) {
			int fu = Fa(u);
			int fv = Fa(v);
			assert(fu != fv);
			ans += (sz[fu]-1) * sz[fv];
			fa[fv] = fu;
			sz[fu] += sz[fv];
			sz[fv] = 0;
		}
	}


	for (int i=1; i<=n; i++) {
		fa[i] = i;
		sz[i] = 1;
	}
	for (int u=1; u<=n; u++) {
		for (int v: graph[u]) if (v < u) {
			int fu = Fa(u);
			int fv = Fa(v);
			assert(fu != fv);
			ans += (sz[fu]-1) * sz[fv];
			fa[fv] = fu;
			sz[fu] += sz[fv];
			sz[fv] = 0;
		}
	}

	for (int i=1; i<=n; i++) {
		ans += 1ll * i * (n-i+1);
	}

	cout <<ans <<"\n";
}



int main()
{
	solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 13020kb

input:

4
2 10 1 1
E 0
T 10
2 10 3 2
E 0
T 10
5 40 5 6
E 0
T 40
T 20
E 30
E 10
10 9 5 6
T 5
E 6
T 7
E 8
T 9
E 0
T 1
E 2
T 3
E 4

output:

20

result:

wrong answer 1st numbers differ - expected: '1', found: '20'