oj.uz

Submission #1105891

# Submission time Handle Problem Language Result Execution time Memory
1105891 2024-10-28T08:41:59 Z vjudge1 Tree Rotations (POI11_rot) C++17
100 / 100
 229 ms 48872 KB 
#include <bits/stdc++.h>

#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define ii pair <int, int>
#define fi first
#define se second
#define ll long long
#define eb emplace_back
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()

using namespace std;

const int mxN = 5e5+5;
const int mxL = 2e5+5;

int n, val[mxN], sub[mxN], tin[mxN], tout[mxN], tour[mxN], Time, cur; ll ans;
vector <int> valN[mxN], ch[mxN];

int newNode() {
    return ++cur;
}

struct fenwickTree {
    int f[mxL];
    void upd(int id, int val) {
        for(; id<mxL; id+=id&-id) f[id]+=val;
    }
    int get(int id) {
        int res = 0;
        for(; id>0; id-=id&-id) res+=f[id];
        return res;
    }
} fwt;

struct reverseFenwickTree {
    int f[mxL];
    void upd(int id, int val) {
        for(; id>0; id-=id&-id) f[id]+=val;
    }
    int get(int id) {
        int res = 0;
        for(; id<mxL; id+=id&-id) res+=f[id];
        return res;
    }
} rfwt;

void input(int node) {
    int x; cin >> x;

    if(x == 0) {
        int lfN = newNode();
        input(lfN);
        int rtN = newNode();
        input(rtN);

        ch[node].eb(lfN);
        ch[node].eb(rtN);
    }
    else {
        val[node] = x;
    }
}

void pre_dfs(int u) {
    tin[u] = ++Time;
    tour[Time] = u;

    sub[u] = 1;
    for(int v:ch[u]) {
        pre_dfs(v);
        sub[u] += sub[v];
    }

    tout[u] = Time;
}

void dfs(int u) {
    int bigCh = -1;
    for(int v:ch[u]) if(bigCh == -1 || sub[v]>sub[bigCh]) bigCh=v;
    for(int v:ch[u]) if(v != bigCh) {
        dfs(v);
        FOR(i,tin[v],tout[v]){
            if(val[tour[i]]) {
                fwt.upd(val[tour[i]], -1);
                rfwt.upd(val[tour[i]], -1);
            }
        }
    }
    if(bigCh != -1) dfs(bigCh);

    /// main solve
    ll res=0, rres=0;

    for(int v:ch[u]) if(v != bigCh) {
        FOR(i,tin[v],tout[v]){
            if(val[tour[i]]) {
                res+=fwt.get(val[tour[i]]-1);
                rres+=rfwt.get(val[tour[i]]+1);
            }
        }
        FOR(i,tin[v],tout[v]){
            if(val[tour[i]]) {
                fwt.upd(val[tour[i]], 1);
                rfwt.upd(val[tour[i]], 1);
            }
        }
    }

    ans += min(res, rres);
    if(val[u]) {
        fwt.upd(val[u], 1);
        rfwt.upd(val[u], 1);
    }
}

int main() {
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    cur = 1; input(1);
    pre_dfs(1);
    dfs(1);
    cout << ans;
}

Compilation message

rot.cpp: In function 'int main()':
rot.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rot.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33104 KB Output is correct
2 Correct 7 ms 33232 KB Output is correct
3 Correct 7 ms 33104 KB Output is correct
4 Correct 7 ms 33360 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33616 KB Output is correct
2 Correct 8 ms 33372 KB Output is correct
3 Correct 8 ms 33616 KB Output is correct
4 Correct 8 ms 33616 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 34384 KB Output is correct
2 Correct 16 ms 33740 KB Output is correct
3 Correct 34 ms 34384 KB Output is correct
4 Correct 12 ms 34128 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 35332 KB Output is correct
2 Correct 30 ms 36688 KB Output is correct
3 Correct 33 ms 37984 KB Output is correct
4 Correct 34 ms 37968 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 42576 KB Output is correct
2 Correct 48 ms 40008 KB Output is correct
3 Correct 64 ms 38216 KB Output is correct
4 Correct 49 ms 37200 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 38224 KB Output is correct
2 Correct 70 ms 39496 KB Output is correct
3 Correct 70 ms 42824 KB Output is correct
4 Correct 63 ms 42312 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 43080 KB Output is correct
2 Correct 120 ms 41832 KB Output is correct
3 Correct 104 ms 42068 KB Output is correct
4 Correct 130 ms 41292 KB Output is correct
5 Correct 195 ms 39780 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 42068 KB Output is correct
2 Correct 113 ms 47768 KB Output is correct
3 Correct 135 ms 45572 KB Output is correct
4 Correct 99 ms 48724 KB Output is correct
5 Correct 229 ms 40788 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 42132 KB Output is correct
2 Correct 106 ms 43104 KB Output is correct
3 Correct 172 ms 41064 KB Output is correct
4 Correct 122 ms 42132 KB Output is correct
5 Correct 112 ms 48872 KB Output is correct
6 Correct 222 ms 41036 KB Output is correct