#include <iostream>
#include <vector>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int c = 1, a[400005], l[400005], r[400005];
ordered_set s[400005];
void trya() {
int h = c, w;
cin >> w;
if (w == 0) {
l[h] = ++c;
trya();
r[h] = ++c;
trya();
}
else a[h] = w;
}
long long int dfs(int x) {
if (l[x] == 0) {
s[x].insert(a[x]);
return 0;
}
long long int res = 0, c = 0, h = 1;
{
int w = l[x];
c += dfs(w);
h *= s[w].size();
int flag = 0;
if (s[w].size() > s[x].size()) {
s[x].swap(s[w]);
flag = 1;
}
for (int v : s[w]) {
if (flag == 1) res += s[x].order_of_key(v);
else res += s[x].size() - s[x].order_of_key(v);
}
for (int v : s[w]) {
s[x].insert(v);
}
}
{
int w = r[x];
c += dfs(w);
h *= s[w].size();
int flag = 0;
if (s[w].size() > s[x].size()) {
s[x].swap(s[w]);
flag = 1;
}
for (int v : s[w]) {
if (flag == 1) res += s[x].order_of_key(v);
else res += s[x].size() - s[x].order_of_key(v);
}
for (int v : s[w]) {
s[x].insert(v);
}
}
return min(res, h - res) + c;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
trya();
cout << dfs(1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
31580 KB |
Output is correct |
2 |
Correct |
22 ms |
31580 KB |
Output is correct |
3 |
Correct |
21 ms |
31580 KB |
Output is correct |
4 |
Correct |
26 ms |
31580 KB |
Output is correct |
5 |
Correct |
22 ms |
31580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
31576 KB |
Output is correct |
2 |
Correct |
21 ms |
31580 KB |
Output is correct |
3 |
Correct |
21 ms |
31580 KB |
Output is correct |
4 |
Correct |
21 ms |
31576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
31832 KB |
Output is correct |
2 |
Correct |
35 ms |
31828 KB |
Output is correct |
3 |
Correct |
21 ms |
31772 KB |
Output is correct |
4 |
Correct |
22 ms |
32088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
32600 KB |
Output is correct |
2 |
Correct |
26 ms |
32604 KB |
Output is correct |
3 |
Correct |
24 ms |
32648 KB |
Output is correct |
4 |
Correct |
25 ms |
32860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
34484 KB |
Output is correct |
2 |
Correct |
37 ms |
35040 KB |
Output is correct |
3 |
Correct |
71 ms |
43344 KB |
Output is correct |
4 |
Correct |
32 ms |
35420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
48212 KB |
Output is correct |
2 |
Correct |
66 ms |
45140 KB |
Output is correct |
3 |
Correct |
77 ms |
47184 KB |
Output is correct |
4 |
Correct |
76 ms |
47804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
53328 KB |
Output is correct |
2 |
Correct |
91 ms |
52560 KB |
Output is correct |
3 |
Correct |
122 ms |
53844 KB |
Output is correct |
4 |
Correct |
86 ms |
47700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
129 ms |
52820 KB |
Output is correct |
2 |
Correct |
123 ms |
54004 KB |
Output is correct |
3 |
Correct |
110 ms |
60632 KB |
Output is correct |
4 |
Correct |
111 ms |
60548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
122 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
156 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
167 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |