Submission #366516

#	Time	Username	Problem	Language	Result	Execution time	Memory
366516		VEGAnn	Papričice (COCI20_papricice)	C++14	0 / 110	4 ms	5228 KiB

papricice

#include <bits/stdc++.h>
#define PB push_back
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int N = 200100;
const int oo = 2e9;
vector<int> g[N];
int tt = 1, n, tin[N], tout[N], siz[N], ms[N];
int ans = oo, glob = -1;

void dfs(int v, int p){
    tin[v] = tt++;

    siz[v] = 1;

    for (int u : g[v]){
        if (u == p) continue;

        dfs(u, v);

        siz[v] += siz[u];
    }

    ms[tin[v]] = siz[v];
    tout[v] = tt - 1;
}

struct seg_tree{
    seg_tree *l, *r;
    int sm;

    seg_tree(): l(0), r(0), sm(0) {}
    seg_tree(seg_tree *v): l(v -> l), r(v -> r), sm(v -> sm) {}

    void build(int tl, int tr){
        if (tl == tr) return;

        l = new seg_tree();
        r = new seg_tree();

        int md = (tl + tr) >> 1;

        l -> build(tl, md);
        r -> build(md + 1, tr);
    }

    void update(int tl, int tr, int ps){
        sm++;

        if (tl == tr) return;

        int md = (tl + tr) >> 1;

        if (ps <= md) {
            l = new seg_tree(l);
            l -> update(tl, md, ps);
        } else {
            r = new seg_tree(r);
            r -> update(md + 1, tr, ps);
        }
    }
};

seg_tree *pref[N];
seg_tree *suf[N];

seg_tree* get_rit(seg_tree *v){
    if (!v)
        return 0;
    else return (v -> r);
}

seg_tree* get_lef(seg_tree *v){
    if (!v)
        return 0;
    else return (v -> l);
}

int get_sum(seg_tree *v){
    return (v ? v -> sm : 0);
}

void real_get_max(seg_tree *v1, seg_tree *v2, int tl, int tr){
    if (tl == tr){
        glob = tl;
        return;
    }

    int md = (tl + tr) >> 1;

    if (get_sum(get_rit(v1)) - get_sum(get_rit(v2)) > 0)
        real_get_max(get_rit(v1), get_rit(v2), md + 1, tr);
    else real_get_max(get_lef(v1), get_lef(v2), tl, md);
}

void real_get_min(seg_tree *v1, seg_tree *v2, int tl, int tr){
    if (tl == tr){
        glob = tl;
        return;
    }

    int md = (tl + tr) >> 1;

    if (get_sum(get_lef(v1)) - get_sum(get_lef(v2)) > 0)
        real_get_min(get_lef(v1), get_lef(v2), tl, md);
    else real_get_min(get_rit(v1), get_rit(v2), md + 1, tr);
}

void get_max(seg_tree *v1, seg_tree *v2, int tl, int tr, int ql, int qr){
    if (ql > qr || glob != -1) return;

    if (tl == ql && tr == qr){
        if (get_sum(v1) - get_sum(v2) > 0)
            real_get_max(v1, v2, tl, tr);

        return;
    }

    int md = (tl + tr) >> 1;

    get_max(get_rit(v1), get_rit(v2), md + 1, tr, max(md + 1, ql), qr);
    get_max(get_lef(v1), get_lef(v2), tl, md, ql, min(qr, md));
}

void get_min(seg_tree *v1, seg_tree *v2, int tl, int tr, int ql, int qr){
    if (ql > qr || glob != -1) return;

    if (tl == ql && tr == qr){
        if (get_sum(v1) - get_sum(v2) > 0)
            real_get_min(v1, v2, tl, tr);

        return;
    }

    int md = (tl + tr) >> 1;

    get_min(get_lef(v1), get_lef(v2), tl, md, ql, min(qr, md));
    get_min(get_rit(v1), get_rit(v2), md + 1, tr, max(md + 1, ql), qr);
}

void last_dfs(int v, int p){
    for (int u : g[v]){
        if (u == p) continue;

        last_dfs(u, v);
    }

    if (siz[v] <= n - siz[v]){
        int SZ = n - siz[v];
        int SE = siz[v];
        int bst = oo;

        {
            // <= SZ / 2

            if (tin[v] > 1){
                glob = -1;
                get_max(pref[tin[v] - 1], NULL, 1, n, 1, SZ / 2);

                if (glob != -1){
                    glob = SZ - glob;

                    if (abs(SE - glob) < abs(SE - bst))
                        bst = glob;
                }
            }

            if (tout[v] < n){
                glob = -1;
                get_max(suf[tout[v] + 1], NULL, 1, n, 1, SZ / 2);

                if (glob != -1){
                    glob = SZ - glob;

                    if (abs(SE - glob) < abs(SE - bst))
                        bst = glob;
                }
            }
        }

        {
            // > SZ / 2

            if (tin[v] > 1){
                glob = -1;
                get_min(pref[tin[v] - 1], NULL, 1, n, SZ / 2 + 1, n);

                if (glob != -1){
                    if (abs(SE - glob) < abs(SE - bst))
                        bst = glob;
                }
            }

            if (tout[v] < n){
                glob = -1;
                get_min(suf[tout[v] + 1], NULL, 1, n, SZ / 2 + 1, n);

                if (glob != -1){
                    if (abs(SE - glob) < abs(SE - bst))
                        bst = glob;
                }
            }
        }

        ans = min(ans, abs(SE - bst));
    }

    if (n - siz[v] <= siz[v]){
        int SZ = siz[v];
        int SE = n - siz[v];
        int bst = oo;

        {
            // <= SZ / 2

            glob = -1;
            get_max(pref[tout[v]], pref[tin[v] - 1], 1, n, 1, SZ / 2);

            if (glob != -1){
                glob = SZ - glob;

                if (abs(SE - glob) < abs(SE - bst))
                    bst = glob;
            }
        }

        {
            // > SZ / 2

            glob = -1;
            get_min(pref[tout[v]], pref[tin[v] - 1], 1, n, SZ / 2 + 1, n);

            if (glob != -1){
                if (abs(SE - glob) < abs(SE - bst))
                    bst = glob;
            }
        }

        ans = min(ans, abs(SE - bst));
    }
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y; x--; y--;

        g[x].PB(y);
        g[y].PB(x);
    }

    dfs(0, -1);

    // build pref && suf

    pref[0] = new seg_tree();
    suf[n + 1] = new seg_tree();

    pref[0] -> build(1, n);
    suf[n + 1] -> build(1, n);

    for (int i = 1; i <= n; i++){
        pref[i] = new seg_tree(pref[i - 1]);

        pref[i] -> update(1, n, ms[i]);
    }

    for (int i = n; i > 0; i--){
        suf[i] = new seg_tree(suf[i + 1]);

        suf[i] -> update(1, n, ms[i]);
    }

    last_dfs(0, -1);

    cout << ans;

    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60