oj.uz

Submission #1105994

# Submission time Handle Problem Language Result Execution time Memory
1105994 2024-10-28T16:15:56 Z InvMOD Tree Rotations (POI11_rot) C++14
100 / 100
 204 ms 48624 KB 
#include<bits/stdc++.h>

// #define int long long

using namespace std;

using ll = long long;

// The memory limit is strict, and max cnt_node is only (n<<2) like segment tree stupid nub InvMOD 28/10/2024 >:(
const int N = 8e5+5, label = 2e5+5;

int n, cnt_node, timerDFS, val[N];

int tin[N], tout[N], tour[N], bit[label];

vector<int> adj[N];

void dfs_Size(int x, int p){
    tour[tin[x] = ++timerDFS] = x;

    for(int v : adj[x])if(v != p) dfs_Size(v, x);

    tout[x] = timerDFS;
    return;
}

void update(int p, int val){
    if(!p) return;
    for(; p <= n; p += p&-p) bit[p] += val;
    return;
}

int get(int p){
    int res = 0;
    if(!p || p < 0) return 0;
    for(; p; p -= p&-p) res += bit[p];
    return res;
}

int get_range(int l, int r){
    return get(r) - get(l-1);
}

void sack_add(int x){
    if(val[x]) update(val[x], 1);
}

void sack_rem(int x){
    if(val[x]) update(val[x], -1);
}

ll sack(int x, int p, bool keep){
    int Mx = 0, hev = 0;
    for(int v : adj[x])if(v != p){
        int szv = tout[v] - tin[v]+1;
        if(szv > Mx) hev = v, Mx = szv;
    }

    ll answer = 0;

    for(int v : adj[x])if(v != p && v != hev) answer = answer + sack(v, x, 0);

    if(hev) answer = answer + sack(hev, x, 1);

    sack_add(x);
    ll left = (val[x] ? get_range(val[x]+1, n) : 0);
    ll right = (val[x] ? get_range(1, val[x]-1) : 0);

    for(int v : adj[x])if(v != p && v != hev){

        for(int i = tin[v]; i <= tout[v]; i++){
            int cur_node = tour[i];
            left = left + 1ll * (val[cur_node] ? get_range(val[cur_node]+1, n) : 0);
            right = right + 1ll * (val[cur_node] ? get_range(1, val[cur_node]-1) : 0);
        }

        for(int i = tin[v]; i <= tout[v]; i++){
            sack_add(tour[i]);
        }
    }

    if(!keep){
        for(int i = tin[x]; i <= tout[x]; i++)
            sack_rem(tour[i]);
    }
    return answer + min(left, right);
}

void input(int cur_node)
{
    int x; cin >> x;
    if(!x){
        // Start 2 new subtree
        for(int i = 0; i < 2; i++){
            adj[cur_node].push_back(++cnt_node);
            input(cnt_node);
        }
    }
    else{
        // Leaf info
        val[cur_node] = x;
    }
    return;
}

void solve()
{
    cin >> n;

    cnt_node = 1;
    input(cnt_node);

    dfs_Size(1, -1);
    cout << sack(1, -1, 0) <<"\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message

rot.cpp: In function 'int32_t main()':
rot.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rot.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27728 KB Output is correct
2 Correct 8 ms 27216 KB Output is correct
3 Correct 6 ms 27728 KB Output is correct
4 Correct 7 ms 27728 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 30800 KB Output is correct
2 Correct 13 ms 29520 KB Output is correct
3 Correct 29 ms 30288 KB Output is correct
4 Correct 13 ms 30556 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 30800 KB Output is correct
2 Correct 28 ms 32848 KB Output is correct
3 Correct 33 ms 34572 KB Output is correct
4 Correct 34 ms 34384 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 40460 KB Output is correct
2 Correct 51 ms 36680 KB Output is correct
3 Correct 55 ms 34216 KB Output is correct
4 Correct 43 ms 32668 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 33352 KB Output is correct
2 Correct 61 ms 35152 KB Output is correct
3 Correct 58 ms 39692 KB Output is correct
4 Correct 56 ms 39248 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 41288 KB Output is correct
2 Correct 107 ms 38968 KB Output is correct
3 Correct 92 ms 39760 KB Output is correct
4 Correct 105 ms 38572 KB Output is correct
5 Correct 160 ms 36688 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 39100 KB Output is correct
2 Correct 109 ms 47088 KB Output is correct
3 Correct 126 ms 43848 KB Output is correct
4 Correct 96 ms 48376 KB Output is correct
5 Correct 201 ms 37448 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 38996 KB Output is correct
2 Correct 101 ms 40264 KB Output is correct
3 Correct 154 ms 37712 KB Output is correct
4 Correct 120 ms 38980 KB Output is correct
5 Correct 103 ms 48624 KB Output is correct
6 Correct 204 ms 37448 KB Output is correct