QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#609730 | #5454. Subtree Activation | Dimash# | 42.857143 | 1039ms | 37156kb | C++23 | 3.2kb | 2024-10-04 13:48:21 | 2024-10-04 13:48:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 12, MOD = (int)1e9 + 7;
int n, tin[N], tout[N], timer = 0, s[N], P[N], pp[N];
ll res = 0;
vector<int> g[N];
void dfs(int v) {
tin[v] = ++timer;
s[v] = 1;
for(int to:g[v]) {
dfs(to);
s[v] += s[to];
}
res += s[v] * 2ll;
tout[v] = ++timer;
}
bool is(int v, int u) {
return (tin[v] <= tin[u] && tout[u] <= tout[v]);
}
ll calc(deque<int> &p) {
ll x = 0;
for(int i = 1; i < n; i++) {
if(is(p[i], p[i - 1])) {
x += 2 * s[p[i - 1]];
} else if(is(p[i - 1], p[i])) {
x += 2 * s[p[i]];
}
}
return x;
}
bool ii = 1;
int l[N], r[N];
bool cmp(int x, int y) {
return s[x] > s[y];
}
int get(int v) {
if(pp[v] == v) return v;
return pp[v] = get(pp[v]);
}
void merge(int a, int b) {
a = get(a);
b = get(b);
pp[a] = b;
}
void test() {
cin >> n;
for(int i = 2; i <= n; i++) {
int p;
cin >> p;
P[i] = p;
g[p].push_back(i);
}
for(int i = 1; i <= n; i++) {
pp[i] = i;
}
dfs(1);
memset(l, -1, sizeof(l));
memset(r, -1, sizeof(r));
vector<int> p(n);
iota(p.begin(), p.end(), 1);
sort(p.begin(), p.end(), cmp);
for(int i:p) {
int v = P[i];
while(v) {
if(get(v) == get(i)) {
v = P[v];
continue;
}
if(l[v] == -1 && r[i] == -1) {
l[v] = i;
r[i] = v;
merge(v, i);
break;
}
else if(r[v] == -1 && l[i] == -1) {
r[v] = i;
l[i] = v;
merge(v, i);
break;
}
v = P[v];
break;
}
v = P[i];
while(v) {
if(get(v) == get(i)) {
v = P[v];
continue;
}
if(l[v] == -1 && l[i] != v && r[i] != v && r[i] == -1) {
l[v] = i;
r[i] = v;
merge(v, i);
break;
}
else if(r[v] == -1 && l[i] != v && r[i] != v && l[i] == -1) {
r[v] = i;
l[i] = v;
merge(v, i);
break;
}
v = P[v];
break;
}
if(l[i] == -1 && r[i] == -1 && i != 1) {
if(l[1] == -1) {
l[1] = i;
r[i] = 1;
merge(i, 1);
} else if(r[1] == -1) {
r[1] = i;
l[i] = 1;
merge(i, 1);
}
}
}
ll x = 0;
for(int i = 1; i <= n; i++) {
if(r[i] != -1) {
if(is(r[i], i)) {
x += 2 * s[i];
} else if(is(i, r[i])) {
x += 2 * s[r[i]];
}
}
}
cout << res - x << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 4.7619
Accepted
time: 0ms
memory: 19548kb
input:
3 1 1
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 4.7619
Accepted
time: 3ms
memory: 19492kb
input:
8 1 2 1 1 5 3 4
output:
20
result:
ok 1 number(s): "20"
Test #3:
score: 4.7619
Accepted
time: 0ms
memory: 19776kb
input:
8 1 2 1 4 5 4 4
output:
20
result:
ok 1 number(s): "20"
Test #4:
score: 4.7619
Accepted
time: 3ms
memory: 19612kb
input:
40 1 1 1 1 1 1 1 1 1 7 11 10 12 13 15 16 16 15 18 20 21 21 21 21 21 21 21 21 21 6 18 28 12 34 22 6 15 23 32
output:
130
result:
ok 1 number(s): "130"
Test #5:
score: 4.7619
Accepted
time: 0ms
memory: 19836kb
input:
40 1 1 1 1 1 1 1 1 1 10 9 12 8 14 15 16 17 12 17 19 21 21 21 21 21 21 21 21 21 23 26 15 9 6 27 32 5 11 8
output:
132
result:
ok 1 number(s): "132"
Test #6:
score: 4.7619
Accepted
time: 2ms
memory: 19540kb
input:
40 1 1 1 1 1 1 1 1 1 6 11 12 13 8 15 15 16 18 17 18 21 21 21 21 21 21 21 21 21 23 13 17 8 20 6 24 27 38 36
output:
132
result:
ok 1 number(s): "132"
Test #7:
score: 4.7619
Accepted
time: 0ms
memory: 19608kb
input:
40 1 1 1 1 1 1 1 1 1 10 11 7 13 14 15 16 17 18 18 18 21 21 21 21 21 21 21 21 21 25 11 13 13 3 24 11 25 35 28
output:
132
result:
ok 1 number(s): "132"
Test #8:
score: 4.7619
Accepted
time: 3ms
memory: 19788kb
input:
40 1 1 1 1 1 1 1 1 1 10 11 12 11 14 14 14 17 16 16 20 21 21 21 21 21 21 21 21 21 17 22 25 14 25 29 23 1 17 14
output:
138
result:
ok 1 number(s): "138"
Test #9:
score: 4.7619
Accepted
time: 0ms
memory: 19564kb
input:
40 1 1 1 1 1 1 1 1 1 7 11 12 12 13 14 13 16 18 19 20 21 21 21 21 21 21 21 21 21 17 8 17 33 27 3 34 20 4 10
output:
126
result:
ok 1 number(s): "126"
Test #10:
score: 0
Wrong Answer
time: 7ms
memory: 19796kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
18876
result:
wrong answer 1st numbers differ - expected: '18824', found: '18876'
Test #11:
score: 0
Wrong Answer
time: 3ms
memory: 19812kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
18998
result:
wrong answer 1st numbers differ - expected: '18914', found: '18998'
Test #12:
score: 0
Wrong Answer
time: 3ms
memory: 19796kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
18926
result:
wrong answer 1st numbers differ - expected: '18854', found: '18926'
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 20044kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
18970
result:
wrong answer 1st numbers differ - expected: '18894', found: '18970'
Test #14:
score: 0
Wrong Answer
time: 7ms
memory: 19880kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
19038
result:
wrong answer 1st numbers differ - expected: '18956', found: '19038'
Test #15:
score: 0
Wrong Answer
time: 3ms
memory: 19748kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
18976
result:
wrong answer 1st numbers differ - expected: '18882', found: '18976'
Test #16:
score: 0
Wrong Answer
time: 1014ms
memory: 29020kb
input:
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
759570
result:
wrong answer 1st numbers differ - expected: '756550', found: '759570'
Test #17:
score: 0
Wrong Answer
time: 1039ms
memory: 37156kb
input:
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
758748
result:
wrong answer 1st numbers differ - expected: '755654', found: '758748'
Test #18:
score: 0
Wrong Answer
time: 1037ms
memory: 29108kb
input:
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
758688
result:
wrong answer 1st numbers differ - expected: '755830', found: '758688'
Test #19:
score: 0
Wrong Answer
time: 1012ms
memory: 29056kb
input:
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
759834
result:
wrong answer 1st numbers differ - expected: '756822', found: '759834'
Test #20:
score: 0
Wrong Answer
time: 1017ms
memory: 28948kb
input:
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
759248
result:
wrong answer 1st numbers differ - expected: '756212', found: '759248'
Test #21:
score: 0
Wrong Answer
time: 1031ms
memory: 37132kb
input:
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
759020
result:
wrong answer 1st numbers differ - expected: '755930', found: '759020'