Submission #992352

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
992352	2024-06-04T09:58:49 Z	SorahISA	Tree Rotations (POI11_rot)	C++17	100 / 100	121 ms	22804 KB

#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA

int N;
i64 ans;
vector<pii> ch;

struct SegTrees {
    
    struct Node {
        int cnt = 0, lt = -1, rt = -1;
        Node (int _cnt = 0, int _lt = -1, int _rt = -1) :
            cnt(_cnt), lt(_lt), rt(_rt) {}
    };
    
    vector<Node> seg;
    deque<int> unused_id;
    int maxn;
    
    void init(int _N) {
        maxn = _N + 1; // (1 << (__lg(_N+1) + 1));
        seg.reserve(4*maxn);
    }
    
    int new_node(int cnt = 0, int lt = -1, int rt = -1) {
        if (SZ(unused_id)) {
            int id = unused_id[0]; unused_id.pf();
            seg[id] = Node(cnt, lt, rt);
            return id;
        }
        seg.eb(cnt, lt, rt);
        return SZ(seg) - 1;
    }
    
    int create_tree(int qX) { return create_tree(qX, 0, maxn-1); }
    int create_tree(int qX, int nL, int nR) {
        // debug(qX, nL, nR);
        if (nL == nR) return new_node(1);

        int nM = (nL + nR) >> 1, lt = -1, rt = -1;
        if (qX <= nM) lt = create_tree(qX, nL,   nM);
        if (nM <  qX) rt = create_tree(qX, nM+1, nR);
        
        return new_node(1, lt, rt);
    }
    
    i64 merge(int L, int R) {
        i64 cost_LR = i64(~seg[L].rt ? seg[seg[L].rt].cnt : 0) * i64(~seg[R].lt ? seg[seg[R].lt].cnt : 0);
        
        seg[L].cnt += seg[R].cnt;
        if (~seg[L].lt and ~seg[R].lt) cost_LR += merge(seg[L].lt, seg[R].lt);
        else                           chmax(seg[L].lt, seg[R].lt);
        if (~seg[L].rt and ~seg[R].rt) cost_LR += merge(seg[L].rt, seg[R].rt);
        else                           chmax(seg[L].rt, seg[R].rt);
        unused_id.eb(R);
        
        return cost_LR;
    }
    
    int dfs(int now) {
        if (now <= N) return create_tree(now);
        
        int lt = dfs(ch[now-N].first);
        int rt = dfs(ch[now-N].second);
        
        i64 cost_sum = i64(seg[lt].cnt) * i64(seg[rt].cnt);
        i64 cost_LR = merge(lt, rt);
        // debug(now, tmp);
        ans += min(cost_LR, cost_sum - cost_LR);
        
        return lt;
    }
};

void solve() {
    cin >> N;
    
    ch.assign(N, {0, 0}); /// offset by -N
    int tok = 2*N;
    function<int()> input = [&]() -> int {
        int id; cin >> id;
        if (id == 0) id = --tok, ch[id-N].first = input(), ch[id-N].second = input();
        return id;
    };
    input();
    // assert(tok == N+1);
    
    function<int(int)> dfs = [&](int now) -> int {
        if (now <= N) return 1;
        int sz_l = dfs(ch[now-N].first), sz_r = dfs(ch[now-N].second);
        if (sz_l < sz_r) swap(ch[now-N].first, ch[now-N].second);
        return sz_l + sz_r;
    };
    dfs(2*N-1);
    
    // debug(ch);
    
    ans = 0;
    SegTrees segs; segs.init(N);
    segs.dfs(2*N-1);
    
    print(ans);
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        // cout << "Case #" << _ << ": ";
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
// using i128 = __int128;
// #define int i64
using f80 = long double;
// using f128 = __float128;
#define double f80
using pii = pair<int, int>;
using pll = pair<i64, i64>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
    static_assert(D >= 1, "Vector dimension must be greater than zero!");
    template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
};

template <typename T> struct Vec<1, T> : vector<T> {
    Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
};

template <class F>
inline constexpr decltype(auto) lambda_fix(F&& f) {
    return [f = std::forward<F>(f)](auto&&... args) {
        return f(f, std::forward<decltype(args)>(args)...);
    };
}

#ifdef local
#define fastIO() void()
#define debug(...) \
    _color.emplace_back("\u001b[31m"), \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), _color.pop_back(), \
    fprintf(stderr, "%s", _color.back().c_str())
#define print(...) \
    fprintf(stdout, "%s", "\u001b[36m"), \
    _P(__VA_ARGS__), \
    fprintf(stdout, "%s", "\u001b[0m")

deque<string> _color{"\u001b[0m"};

template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) {begin(_t);};

template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t);
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu);

inline void _do() {cerr << "\n";};
template <typename T> inline void _do(T &&_t) {_print_err(_t), cerr << "\n";}
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) {_print_err(_t), cerr << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#endif

inline void _P() {cout << "\n";};
template <typename T> inline void _P(T &&_t) {cout << _t << "\n";}
template <typename T, typename ...U> inline void _P(T &&_t, U &&..._u) {cout << _t << " ", _P(_u...);}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int getRand(int L, int R) {
    if (L > R) swap(L, R);
    return (int)(rng() % ((uint64_t)R - L + 1) + L);
}

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

/// below are Fast I/O and _print_err templates ///

/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///

#include <unistd.h>

const int S = 65536;

int OP = 0;
char OB[S];

inline char RC() {
    static char buf[S], *p = buf, *q = buf;
    return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}

inline int RI() {
    static char c;
    int a;
    while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
    if (c == '-') {
        a = 0;
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
    }
    else {
        a = c ^ '0';
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
    }
    return a;
}

inline void WI(int n, char c = '\n') {
    static char buf[20], p;
    if (n == 0) OB[OP++] = '0';
    p = 0;
    if (n < 0) {
        OB[OP++] = '-';
        while (n) buf[p++] = '0' - (n % 10), n /= 10;
    }
    else {
        while (n) buf[p++] = '0' + (n % 10), n /= 10;
    }
    for (--p; p >= 0; --p) OB[OP++] = buf[p];
    OB[OP++] = c;
    if (OP > S-20) write(1, OB, OP), OP = 0;
}

/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/

#ifdef local

template <typename T> inline void _print_err(T &&_t) {cerr << _t;}

template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.emplace_back(_tmp_color);
    cerr << _color.back() << "[";
    for (bool _first = true; auto &_x : _t) {
        if (!_first) cerr << ", ";
        _print_err(_x), _first = false;
    }
    cerr << "]" << (_color.pop_back(), _color.back());
}

template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.emplace_back(_tmp_color);
    cerr << _color.back() << "(";
    _print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
    cerr << ")" << (_color.pop_back(), _color.back());
    return os;
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
    cerr << ")" << (_color.pop_back(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.emplace_back(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
    cerr << ")" << (_color.pop_back(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.emplace_back(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

#endif

#endif

Subtask #1
9.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1892 KB	Output is correct
2	Correct	6 ms	1116 KB	Output is correct
3	Correct	16 ms	2220 KB	Output is correct
4	Correct	6 ms	1888 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	3156 KB	Output is correct
2	Correct	26 ms	4900 KB	Output is correct
3	Correct	27 ms	7516 KB	Output is correct
4	Correct	26 ms	6952 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	13920 KB	Output is correct
2	Correct	39 ms	10076 KB	Output is correct
3	Correct	48 ms	7004 KB	Output is correct
4	Correct	36 ms	5108 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	6736 KB	Output is correct
2	Correct	59 ms	8284 KB	Output is correct
3	Correct	52 ms	13908 KB	Output is correct
4	Correct	51 ms	13540 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	15528 KB	Output is correct
2	Correct	74 ms	10944 KB	Output is correct
3	Correct	91 ms	12112 KB	Output is correct
4	Correct	81 ms	12624 KB	Output is correct
5	Correct	99 ms	11856 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	12176 KB	Output is correct
2	Correct	96 ms	21588 KB	Output is correct
3	Correct	108 ms	16316 KB	Output is correct
4	Correct	88 ms	22804 KB	Output is correct
5	Correct	121 ms	13468 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	14408 KB	Output is correct
2	Correct	111 ms	12624 KB	Output is correct
3	Correct	118 ms	12372 KB	Output is correct
4	Correct	108 ms	14420 KB	Output is correct
5	Correct	103 ms	21180 KB	Output is correct
6	Correct	86 ms	14672 KB	Output is correct

Submission #992352

Compilation message