QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #609420 | #5454. Subtree Activation | Dimash# | 33.333333 | 0ms | 3832kb | C++23 | 1.5kb | 2024-10-04 12:52:21 | 2024-10-04 12:52:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e2 + 12, MOD = (int)1e9 + 7;
int n, tin[N], tout[N], timer = 0, s[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;
}
ll dp[N][2];
void go(int v) {
ll sum = 0;
vector<ll> d;
for(int to:g[v]) {
go(to);
sum += dp[to][1];
d.push_back(dp[to][0] - dp[to][1] + s[to] * 2);
}
sort(d.rbegin(), d.rend());
dp[v][1] = dp[v][0] = sum;
for(int i = 0; i < min((int)d.size(), 2) && d[i] >= 0; i++) {
if(i <= 0) {
dp[v][0] += d[i];
}
dp[v][1] += d[i];
}
}
void test() {
cin >> n;
for(int i = 2; i <= n; i++) {
int p;
cin >> p;
g[p].push_back(i);
}
dfs(1);
go(1);
cout << res - max(dp[1][1], dp[1][0]) << '\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: 3832kb
input:
3 1 1
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 4.7619
Accepted
time: 0ms
memory: 3544kb
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: 3548kb
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: 3816kb
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: 3812kb
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: 3532kb
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: 3784kb
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: 3780kb
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: 0ms
memory: 3616kb
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
Runtime Error
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:
result:
Test #11:
score: 0
Runtime Error
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:
result:
Test #12:
score: 0
Runtime Error
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:
result:
Test #13:
score: 0
Runtime Error
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:
result:
Test #14:
score: 0
Runtime Error
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:
result:
Test #15:
score: 0
Runtime Error
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:
result:
Test #16:
score: 0
Runtime Error
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:
result:
Test #17:
score: 0
Runtime Error
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:
result:
Test #18:
score: 0
Runtime Error
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:
result:
Test #19:
score: 0
Runtime Error
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:
result:
Test #20:
score: 0
Runtime Error
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:
result:
Test #21:
score: 0
Runtime Error
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...