QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#609659 | #5454. Subtree Activation | Dimash# | 33.333333 | 30ms | 36936kb | C++23 | 2.9kb | 2024-10-04 13:39:45 | 2024-10-04 13:39:46 |
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];
}
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];
}
P[i] = P[v];
}
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;
}
詳細信息
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: 0ms
memory: 19840kb
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: 19604kb
input:
8 1 2 1 4 5 4 4
output:
20
result:
ok 1 number(s): "20"
Test #4:
score: 4.7619
Accepted
time: 0ms
memory: 19488kb
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: 19600kb
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: 0ms
memory: 19760kb
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: 19760kb
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: 0
Wrong Answer
time: 0ms
memory: 19820kb
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:
142
result:
wrong answer 1st numbers differ - expected: '138', found: '142'
Test #9:
score: 0
Wrong Answer
time: 4ms
memory: 19792kb
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:
134
result:
wrong answer 1st numbers differ - expected: '126', found: '134'
Test #10:
score: 0
Wrong Answer
time: 0ms
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:
18892
result:
wrong answer 1st numbers differ - expected: '18824', found: '18892'
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 19872kb
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:
19030
result:
wrong answer 1st numbers differ - expected: '18914', found: '19030'
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 20048kb
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:
18948
result:
wrong answer 1st numbers differ - expected: '18854', found: '18948'
Test #13:
score: 0
Wrong Answer
time: 0ms
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:
18982
result:
wrong answer 1st numbers differ - expected: '18894', found: '18982'
Test #14:
score: 0
Wrong Answer
time: 5ms
memory: 19808kb
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:
19070
result:
wrong answer 1st numbers differ - expected: '18956', found: '19070'
Test #15:
score: 0
Wrong Answer
time: 0ms
memory: 19780kb
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:
18992
result:
wrong answer 1st numbers differ - expected: '18882', found: '18992'
Test #16:
score: 0
Wrong Answer
time: 27ms
memory: 31168kb
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:
759606
result:
wrong answer 1st numbers differ - expected: '756550', found: '759606'
Test #17:
score: 0
Wrong Answer
time: 28ms
memory: 35192kb
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:
758782
result:
wrong answer 1st numbers differ - expected: '755654', found: '758782'
Test #18:
score: 0
Wrong Answer
time: 30ms
memory: 32600kb
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:
758722
result:
wrong answer 1st numbers differ - expected: '755830', found: '758722'
Test #19:
score: 0
Wrong Answer
time: 28ms
memory: 36936kb
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:
759888
result:
wrong answer 1st numbers differ - expected: '756822', found: '759888'
Test #20:
score: 0
Wrong Answer
time: 26ms
memory: 32580kb
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:
759276
result:
wrong answer 1st numbers differ - expected: '756212', found: '759276'
Test #21:
score: 0
Wrong Answer
time: 28ms
memory: 32516kb
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:
759082
result:
wrong answer 1st numbers differ - expected: '755930', found: '759082'