QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562253 | #9261. Toll Road | Baneist# | WA | 0ms | 13020kb | C++14 | 1.1kb | 2024-09-13 16:07:32 | 2024-09-13 16:07:36 |
Judging History
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'