#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
#define pb push_back
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
#define sqr(x) (x)*(x)
#define fi first
#define se second
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l,int r){return l+((hdp()%(r-l+1))+r-l+1)%(r-l+1);}
const int N = 4e5 + 5;
const int mod = 998244353;
const int SQ = 450;
const int inf = 1e9;
const int bound = 1e7;
vector<int> g[N];
int n,m,c[N],sz[N],par[N];
vector<int> V[N];
stack<int> st;
long long dp[N];
int bit[N];
void upd(int i)
{
for(;i<=n;i+=i&-i)
{
st.push(i);
bit[i]++;
}
}
int get(int i)
{
int res=0;
for(;i;i-=i&-i) res+=bit[i];
return res;
}
void dfs(int u=1,int p=0,bool keep=0)
{
int bc=0;
for(int v:g[u]) if(v!=p&&sz[v]>sz[bc]) bc=v;
for(int v:g[u]) if(v!=p&&v!=bc) dfs(v,u,0);
if(bc)
{
dfs(bc,u,1);
swap(V[u],V[bc]);
dp[u]=dp[bc];
}
for(int v:g[u]) if(v!=p&&v!=bc) dp[u]+=dp[bc];
long long sum1=0,sum2=0,xx=V[u].size();
for(int v:g[u]) if(v!=bc) for(auto t:V[v])
{
V[u].pb(t);
int x=get(t);
sum1+=x;
sum2+=xx-x;
}
dp[u]+=min(sum1,sum2);
for(int v:g[u]) if(v!=bc) for(auto t:V[v]) upd(t);
if(c[u])
{
V[u].pb(c[u]);
upd(c[u]);
}
if(!keep)
{
while(!st.empty())
{
bit[st.top()]=0;
st.pop();
}
}
}
void dfs_sz(int u=1,int p=0)
{
sz[u]=1;
for(auto v:g[u]) if(v!=p)
{
dfs_sz(v,u);
sz[u]+=sz[v];
}
}
signed main()
{
if (fopen("in.txt", "r")) {
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
fastIO
cin>>n;
int u=0,v;
while(cin>>v)
{
++m;
g[u].pb(m);
par[m]=u;
if(v)
{
c[m]=v;
while(g[u].size()==2) u=par[u];
if(!u) break;
}
else u=m;
}
dfs_sz();
dfs();
cout<<dp[1];
}
Compilation message
rot.cpp: In function 'int main()':
rot.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | freopen("in.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
rot.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | freopen("out.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
20056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
22364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
27600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
42948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
37576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
54980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
51136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
52444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
