Submission #1020746

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1020746	2024-07-12T09:11:35 Z	kustizus	Tree Rotations (POI11_rot)	C++17	100 / 100	229 ms	34900 KB

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,fma,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=4e5;
vector <int> v,g[N+5];
int n,x,idx=0,cnt[N+5],sz[N+5],sum[N+5],FT[N+5];
void input(){
    int x;
    cin>>x;
    cnt[idx]=x;
    if (x) return;
    int nw=idx;
    g[nw].push_back(++idx);
    input();
    g[nw].push_back(++idx);
    input();
}
void dfs(int i){
    if (cnt[i]){
        sz[i]=1;
        return;
    }
    for (int x : g[i]){
        dfs(x);
        sz[i]+=sz[x];
    }
}
void Update(int pos, int val){
    for (;pos<=N;pos+=pos&(-pos)) FT[pos]+=val;
}
int Get(int pos){
    int val=0;
    for (;pos;pos-=pos&(-pos)) val+=FT[pos];
    return val;
}
void cl(int i, int val){
    if (cnt[i]){
        Update(cnt[i],val);
        return;
    }
    for (int x : g[i]) cl(x,val);
}
int lh,nh;
void Cal(int i){
    if (cnt[i]){
        lh+=Get(cnt[i]);
        nh+=Get(n)-Get(cnt[i]);
        return;
    }
    for (int x : g[i]) Cal(x);
}
void dfs1(int i){
    if (cnt[i]){
        Update(cnt[i],1);
        return;
    }
    int x=g[i][0];
    int y=g[i][1];
    if (sz[x]>sz[y]) swap(x,y);
    dfs1(x);
    sum[i]+=sum[x];
    cl(x,-1);
    dfs1(y);
    sum[i]+=sum[y];
    lh=nh=0;
    Cal(x);
    cl(x,1);
    sum[i]+=min(lh,nh);
}
void Solve(){
    cin>>n;
    input();
    dfs(0);
    dfs1(0);
    cout<<sum[0];
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen ("FILE.INP","r",stdin);
    // freopen ("FILE.OUT","w",stdout);
    int t=1;
    // cin>>t;
    while (t--) Solve();
    cerr<<"\nTIME: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	10072 KB	Output is correct
2	Correct	4 ms	9816 KB	Output is correct
3	Correct	5 ms	9820 KB	Output is correct
4	Correct	4 ms	9816 KB	Output is correct
5	Correct	4 ms	9820 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9820 KB	Output is correct
2	Correct	4 ms	9820 KB	Output is correct
3	Correct	4 ms	9820 KB	Output is correct
4	Correct	4 ms	9820 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9816 KB	Output is correct
2	Correct	5 ms	9820 KB	Output is correct
3	Correct	4 ms	9820 KB	Output is correct
4	Correct	4 ms	9820 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	10332 KB	Output is correct
2	Correct	7 ms	10256 KB	Output is correct
3	Correct	5 ms	10408 KB	Output is correct
4	Correct	6 ms	10332 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	11356 KB	Output is correct
2	Correct	14 ms	10900 KB	Output is correct
3	Correct	28 ms	12624 KB	Output is correct
4	Correct	11 ms	11356 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	14420 KB	Output is correct
2	Correct	29 ms	15444 KB	Output is correct
3	Correct	31 ms	16724 KB	Output is correct
4	Correct	32 ms	16980 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	22096 KB	Output is correct
2	Correct	40 ms	20308 KB	Output is correct
3	Correct	50 ms	18848 KB	Output is correct
4	Correct	40 ms	18272 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	21072 KB	Output is correct
2	Correct	52 ms	22032 KB	Output is correct
3	Correct	60 ms	24400 KB	Output is correct
4	Correct	54 ms	24288 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	28496 KB	Output is correct
2	Correct	101 ms	27392 KB	Output is correct
3	Correct	82 ms	27440 KB	Output is correct
4	Correct	105 ms	26848 KB	Output is correct
5	Correct	163 ms	25680 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	28300 KB	Output is correct
2	Correct	103 ms	33104 KB	Output is correct
3	Correct	112 ms	31568 KB	Output is correct
4	Correct	85 ms	33804 KB	Output is correct
5	Correct	208 ms	27984 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	107 ms	28732 KB	Output is correct
2	Correct	92 ms	30288 KB	Output is correct
3	Correct	152 ms	28756 KB	Output is correct
4	Correct	117 ms	29008 KB	Output is correct
5	Correct	90 ms	34900 KB	Output is correct
6	Correct	229 ms	28888 KB	Output is correct

Submission #1020746

Compilation message