#include "bits/stdc++.h"
using namespace std;
#ifdef N_N_C
#include "debug.h"
#else
#define cebug(...) "Arya"
#endif
#define ll long long
const int N=2e5+5;
const int mod=1e9+7;
int n,node=1,a[N],sz[N],cur,cur2,leaf[N];
ll ans[N];
vector <int> g[N];
struct BIT{
#define gb(x) (x&(-x))
int n;
vector <int> bit;
void init(int _n){
bit.resize(_n,0);
n=_n;
}
void update(int pos, int val){
int i=pos;
for (; i<n; i+=gb(i)) bit[i]+=val;
}
int get(int pos){
int ans=0,i=pos;
for (; i>=1; i-=gb(i)) ans+=bit[i];
return ans;
}
}fw;
struct BIT2{
#define gb(x) (x&(-x))
int n;
vector <int> bit;
void init(int _n){
bit.resize(_n,0);
n=_n;
}
void update(int pos, int val){
int i=pos;
for (; i; i-=gb(i)) bit[i]+=val;
}
int get(int pos){
int ans=0,i=pos;
for (; i<n; i+=gb(i)) ans+=bit[i];
return ans;
}
}fw2;
void input(){
int x;
cin>>x;
a[node]=x;
if(x) return;
int nw=node;
g[nw].push_back(++node);
input();
g[nw].push_back(++node);
input();
}
void pre_dfs(int u){
if(a[u]) leaf[u]=1;
sz[u]=1;
for(auto v:g[u]){
pre_dfs(v);
sz[u]+=sz[v];
leaf[u]+=leaf[v];
}
}
void add(int u){
if(a[u]) cur+=fw.get(a[u]-1),cur2+=fw2.get(a[u]+1);
for(auto v:g[u]) add(v);
}
void del(int u){
if(a[u]) fw.update(a[u],-1),fw2.update(a[u],-1);
for(auto v:g[u]) del(v);
}
void upd(int u){
if(a[u]) fw.update(a[u],1),fw2.update(a[u],1);
for(auto v:g[u]) upd(v);
}
void dfs(int u){
if(a[u]){
fw.update(a[u],1);
fw2.update(a[u],1);
return;
}
int big=0,small=0;
cur=0;
cur2=0;
for(auto v:g[u]) if(sz[v]>sz[big]) big=v;
for(auto v:g[u]){
if(v!=big){
dfs(v);
del(v);
}
}
assert(big);
dfs(big);
for(auto v:g[u]) if(v!=big) add(v),upd(v),small=v;
assert(small);
ans[u]=ans[small]+ans[big]+min(cur,cur2);
cebug(u,cur,cur2);
//cout << u << " " << ans[u] << " " << a[big] << " " << a[small] << "\n";
}
void sol(){
fw.init(N);
fw2.init(N);
cin>>n;
input();
pre_dfs(1);
dfs(1);
cout<<ans[1];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen(".inp", "r", stdin);
// freopen(".out", "w", stdout);
int tt=1;
//cin>>tt;
while(tt--){
sol();
}
cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
return 0;
}
Compilation message
rot.cpp: In function 'void dfs(int)':
rot.cpp:7:20: warning: statement has no effect [-Wunused-value]
7 | #define cebug(...) "Arya"
| ^~~~~~
rot.cpp:107:2: note: in expansion of macro 'cebug'
107 | cebug(u,cur,cur2);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
8284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
10712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
18900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
22160 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
22096 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
23644 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
23048 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
