제출 #376336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376336		lyc	Papričice (COCI20_papricice)	C++14	15 / 110	10 ms	8940 KiB

papricice

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int mxN = 2e5+5;

int N;
vector<int> al[mxN];
int pre[mxN], pst[mxN], cnt, sub[mxN], ans;

struct node {
    int s, e, m, v;
    node *l, *r;
    node(int s, int e): s(s), e(e), m((s+e)/2), v(0) {
        if (s != e) {
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }

    node(node* n): s(n->s), e(n->e), m(n->m), v(n->v), l(n->l), r(n->r) {}

    node* update(int a, int b) {
        node *n = new node(this);
        if (s == e) {
            n->v += b;
        } else {
            if (a <= m) n->l = l->update(a,b);
            else n->r = r->update(a,b);
            n->v = n->l->v + n->r->v;
        }
        return n;
    }
} *rootdown[mxN];

int lower(node *p, node *q, int a) {
    if (p->s == p->e) return (q->v - p->v) ? p->s : 0;
    int x = 0;
    if (a > p->m) x = lower(p->r, q->r, a);
    if (x == 0 && (q->l->v - p->l->v) > 0) x = lower(p->l, q->l, a);
    return x;
}

int upper(node *p, node *q, int a) {
    if (p->s == p->e) return (q->v - p->v) ? p->s : mxN;
    int x = mxN;
    if (a <= p->m) x = upper(p->l, q->l, a);
    if (x == mxN && (q->r->v - p->r->v) > 0) x = upper(p->r, q->r, a);
    return x;
}

int calc(int a, int b, int c) {
    return max({a,b,c}) - min({a,b,c});
}

int dfs(int u, int p) {
    pre[u] = ++cnt;
    sub[u] = 1;
    for (int& v : al[u]) if (v != p) {
        sub[u] += dfs(v,u);
    }
    pst[u] = cnt;
    return sub[u];
}

void dfs2(int u, int p, node* rootup) {
    if (p != -1) {
        rootup = rootup->update(sub[u],-1);
    }

    int x = N-sub[u];
    int a = lower(rootdown[0], rootup, x/2);
    int b = upper(rootdown[0], rootup, (x+1)/2);
    //TRACE(u _ x _ a _ b);
    if (a >= 1) ans = min(ans, calc(sub[u], a, x-a));
    if (b <= N) ans = min(ans, calc(sub[u], b, x-b));

    if (N-sub[u]) {
        rootup = rootup->update(N-sub[u],1);
    }
    for (int& v : al[u]) if (v != p) {
        rootup = rootup->update(sub[v],1);
    }
    for (int& v : al[u]) if (v != p) {
        dfs2(v, u, rootup);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N;
    FOR(i,1,N-1){
        int X, Y; cin >> X >> Y;
        al[X].push_back(Y);
        al[Y].push_back(X);
    }

    ans = N+1;
    rootdown[0] = new node(1,N);

    cnt = 0;
    dfs(1,-1);
    dfs2(1,-1, new node(1,N));
    cout << ans << '\n';
}

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