This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=4e5+5;
int n, bit[nx], root, cur, sz[nx];
vector<int> adj[nx], a[nx];
bool big[nx];
ll ans=0;
void upd(int x, int val)
{
for(; x <= n; x+=x&-x)
bit[x]+=val;
}
int get(int x)
{
int res=0;
for(; x > 0; x-=x&-x)
res+=bit[x];
return res;
}
int go()
{
int u;
cin>>u;
if(!u)
{
int l=go();
int r=go();
cur++;
adj[cur].emplace_back(l);
adj[cur].emplace_back(r);
return cur;
}
else return u;
}
int dfs1(int u)
{
sz[u]=1;
for(int v:adj[u])
sz[u]+=dfs1(v);
return sz[u];
}
void add(int u, int x)
{
upd(u, x);
for(int v:adj[u])
if(!big[v])
add(v, x);
}
void dfs(int u, bool keep)
{
if(u<=n)
a[u].emplace_back(u);
int mx=-1, bc=-1, sc=-1;
for(int v:adj[u])
if(sz[v]>mx)
mx=sz[v], bc=v;
for(int v:adj[u])
if(v!=bc)
dfs(v, 0), sc=v;
if(bc!=-1)
dfs(bc, 1), big[bc]=1;
if(sc!=-1)
{
ll l=0, r=0;
for(int c:a[sc])
l+=get(c-1), r+=get(n)-get(c);
ans+=min(l, r);
}
if(bc!=-1 && sc!=-1)
{
swap(a[u], a[bc]);
for(int c:a[sc])
a[u].emplace_back(c);
a[sc].clear();
}
add(u, 1);
if(bc!=-1)
big[bc]=0;
if(!keep)
add(u, -1);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n;
cur=n;
root=go();
dfs1(root);
dfs(root, 0);
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |