oj.uz

Submission #1020426

# Submission time Handle Problem Language Result Execution time Memory
1020426 2024-07-12T04:22:12 Z coldbr3w Tree Rotations (POI11_rot) C++17
0 / 100
 44 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 1e6 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 450;
ll n, m, res = 0;
ll a[N], sz[N], heavy[N];
vector<ll>adj[N];
set<ll>s[N];
struct fenwick_tree{
    ll n;
    vector<ll>ft;
    void init(ll _n){
        n = _n;
        ft.resize(n + 10);
    }
    void update(ll idx, ll val){
        while(idx <= n){
            ft[idx] += val;
            idx += (idx & (-idx));
        }
    }
    ll get(ll idx){
        ll res = 0;
        while(idx > 0){
            res += ft[idx];
            idx -= (idx & (-idx));
        }
        return res;
    }
} ft;
ll idx = 1;
void input(){
    ll x; cin >> x;
    a[idx] = x;
    if(x != 0) return;
    ll cur = idx;
    idx++;
    adj[cur].pb(idx);
    input();
    idx++;
    adj[cur].pb(idx);
    input();
}
void pre_dfs(ll u, ll par){
    sz[u] = 1;
    for(auto v : adj[u]){
        if(v == par) continue;
        pre_dfs(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[heavy[u]]) heavy[u] = v;
    }
}
void change(ll u, ll par, ll val){
    if(a[u] > 0) ft.update(a[u], val);
    for(auto v : adj[u]){
        if(v != par) change(v, u, val);
    }
}
void dfs(ll u, ll par){
    if(a[u] != 0){
        s[u].insert(a[u]);
        ft.update(a[u], 1);
        return;
    }
    for(auto v : adj[u]){
        if(v != heavy[u] && v != par){
            dfs(v, u);
            change(v, u, -1);
            if(s[u].size() < s[v].size()) swap(s[u], s[v]);
            for(auto x : s[v]) s[u].insert(x);
        }
    }
    dfs(heavy[u], u);
    ll inv = 0;
    for(auto x : s[u]){
        inv = (inv + ft.get(x - 1));
    }
    if(s[heavy[u]].size() > s[u].size()) swap(s[heavy[u]], s[u]);
    for(auto x : s[heavy[u]]) s[u].insert(x);
    for(auto v : adj[u]){
        if(v != par && v != heavy[u]) change(v, u, 1);
    }
    ll cur_sz = s[u].size();
    res += min(cur_sz * (cur_sz - 1) / 2 - inv, inv);
}
void to_thic_cau(){
    ll n; cin >> n;
    input();
    ft.init(idx);
    pre_dfs(1, 0);
    for(int i = 1; i <= idx;i++) {
        sort(all(adj[i]), [&](const ll &a, const ll &b){
            return sz[a] < sz[b];
        });
    }
    dfs(1, 0);
    cout << res << '\n';
}   

signed main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -