제출 #133829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133829		osaaateiasavtnl	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	6 ms	4216 KiB

catdog

#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
mt19937 rnd(228);
struct Node {
    int x, y, cnt;
    Node *l, *r;
    Node (int x_) {
        x = x_; y = rnd();
        l = r = NULL;
        cnt = 1;
    }   
};  
int cnt(Node *t) {
    if (!t) return 0;
    else return t->cnt;
}   
void relax(Node *t) {
    t->cnt = cnt(t->l) + cnt(t->r) + 1;
}   
Node *merge(Node *l, Node *r) {
    if (!l) return r;
    if (!r) return l;
    if (l->y < r->y) {
        l->r = merge(l->r, r);
        relax(l);
        return l;
    }  
    else {
        r->l = merge(l, r->l);
        relax(r);
        return r;
    }   
}   
pair <Node*, Node*> split(Node *t, int x) {
    if (!t) return {NULL, NULL};
    if (t->x < x) {
        auto tmp = split(t->r, x);
        t->r = tmp.first;
        relax(t);
        return {t, tmp.second};
    }
    else {
        auto tmp = split(t->l, x);
        t->l = tmp.second;
        relax(t);
        return {tmp.first, t};
    }   
}
void insert(Node *&t, int x) {
    auto tmp = split(t, x);
    t = merge(merge(tmp.first, new Node(x)), tmp.second);
}   
void erase(Node *&t, int x) {
    auto tmp = split(t, x);
    auto tmp1 = split(tmp.second, x + 1);
    t = merge(tmp.first, tmp1.second);
}   
Node *get(Node *&t, int l, int r) {
    auto tmp = split(t, l);
    auto tmp1 = split(tmp.second, r + 1);
    t = merge(tmp.first, tmp1.second);
    return tmp1.first;
}   
const int N = 1e5 + 7;
Node *dd[N][2];
vector <int> g[N];
int vert[N];
int l[N], r[N], ptr = 0;
void dfs(int u, int p) {
    l[u] = ++ptr;
    vert[ptr] = u;
    for (int v : g[u]) {
        if (v != p) {
            dfs(v, u);
        }   
    }   
    r[u] = ptr;
}
int mx[N << 2];
void upd(int v, int tl, int tr, int p, int x) {
    if (tl == tr) {
        mx[v] = x;
        return;
    }   
    int tm = (tl + tr) >> 1;
    if (p <= tm) upd(v * 2 + 1, tl, tm, p, x);
    else upd(v * 2 + 2, tm + 1, tr, p, x);
    mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}   
int parent(int v, int tl, int tr, int l, int r, int x) {
    if (tr < l || r < tl || mx[v] < x) return -1;
    if (tl == tr) return vert[tl];
    int tm = (tl + tr) >> 1;
    int t = parent(v * 2 + 2, tm + 1, tr, l, r, x);
    if (t != -1) return t;
    else return parent(v * 2 + 1, tl, tm, l, r, x);
}   
int ans = 0;
void initialize(int n, vector <int> a, vector <int> b) {
    for (int i = 0; i < n - 1; ++i) {
        g[a[i]].app(b[i]);
        g[b[i]].app(a[i]);
    }   
    ++n;
    g[0].app(1);
    dfs(0, 0);
    for (int i = 0; i < (N << 2); ++i) {
        mx[i] = -1;
    }   
    upd(0, 0, N, l[0], r[0]);
}   
//0 - cat, 1 - dog
int type[N];
void add(int u) {
    int p = parent(0, 0, N, 0, l[u] - 1, r[u]);
    ans += type[u] ^ type[p];
    for (int i = 0; i < 2; ++i) {
        dd[u][i] = get(dd[p][i], l[u], r[u]);        
        if (type[u] ^ type[p]) {
            if (i == type[u]) {
                ans -= cnt(dd[u][i]);
            }   
            else {
                ans += cnt(dd[u][i]);
            }   
        } 
    }   
    insert(dd[p][type[u]], l[u]);
    upd(0, 0, N, l[u], r[u]);
}   
void del(int u) {
    int p = parent(0, 0, N, 0, l[u] - 1, r[u]);
    ans -= type[u] ^ type[p];
    erase(dd[p][type[u]], l[u]);
    for (int i = 0; i < 2; ++i) {
        if (type[u] ^ type[p]) {
            if (i == type[u]) {
                ans += cnt(dd[u][i]);
            }   
            else {
                ans -= cnt(dd[u][i]);
            }   
        }   
        auto tmp = split(dd[p][i], l[u]);
        auto tmp1 = split(dd[p][i], r[u] + 1);
        dd[p][i] = merge(merge(tmp.first, dd[u][i]), tmp1.second);
        dd[u][i] = NULL;
    }   
    upd(0, 0, N, l[u], -1);
}   
int f() {
    #ifdef HOME0
    cout << ans << ' ' << cnt(dd[0][0]) << ' ' << cnt(dd[0][1]) << '\n';
    #endif
    return ans - cnt(dd[0][1]) + min(cnt(dd[0][0]), cnt(dd[0][1]));
}   
int cat(int u) {
    type[u] = 0;
    add(u);
    return f();
}
int dog(int u) {
    type[u] = 1;
    add(u);    
    return f();
}
int neighbor(int u) {
    del(u);
    return f();        
}   
#ifdef HOME
signed main() {
    freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    vector <int> a, b;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        a.app(u); b.app(v);
    }   
    initialize(n, a, b);
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int t, u;
        cin >> t >> u;
        if (t == 1) cout << cat(u) << '\n';
        else if (t == 2) cout << dog(u) << '\n';
        else cout << neighbor(u) << '\n';
    }   
}       
#endif

• Subtask 1: 0 / 8
• Subtask 2: 0 / 30
• Subtask 3: 0 / 62