Submission #1119589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119589		Zero_OP	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	192 ms	29044 KiB

catdog

#include <bits/stdc++.h>

#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

const int MAX = 1e5 + 5;

int N, sz[MAX], head[MAX], par[MAX], heavy[MAX], pos[MAX], sz_chain[MAX], t[MAX];
vector<int> adj[MAX];

struct node{
    int a[2][2];
    node(){
        for(int i = 0; i < 2; ++i){
            for(int j = 0; j < 2; ++j){
                a[i][j] = MAX;
            }
        }
    }

    friend node operator + (const node& a, const node& b){
        node c;
        for(int i = 0; i < 2; ++i){
            for(int j = 0; j < 2; ++j){
                for(int k = 0; k < 2; ++k){
                    for(int l = 0; l < 2; ++l){
                        c.a[i][l] = min(c.a[i][l], a.a[i][j] + b.a[k][l] + (k != j));
//                        cout << i << ' ' << j << ' ' << k << ' ' << l << " -> " << i << ' ' << l << '\n';
                    }
                }
            }
        }
        return c;
    }

    void debug(){
        cout << "[" << a[0][0] << ", " << a[0][1] << ", " << a[1][0] << ", " << a[1][1] << "]\n";
    }
};

struct segment_tree{
    vector<node> st;
    segment_tree(int n) : st(n << 2) {}
    segment_tree() : st(0) {}

    void update(int id, int l, int r, int pos, int v_cat, int v_dog){
        if(l == r){
            st[id].a[0][0] += v_cat;
            st[id].a[1][1] += v_dog;
        } else{
            int mid = l + r >> 1;
            if(pos <= mid) update(id << 1, l, mid, pos, v_cat, v_dog);
            else update(id << 1 | 1, mid + 1, r, pos, v_cat, v_dog);
            st[id] = st[id << 1] + st[id << 1 | 1];
        }
    }

    void build(int id, int l, int r){
        if(l == r){
            st[id].a[0][0] = 0;
            st[id].a[1][1] = 0;
            st[id].a[0][1] = MAX;
            st[id].a[1][0] = MAX;
        } else{
            int mid = l + r >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
            st[id] = st[id << 1] + st[id << 1 | 1];
        }
    }

    node get(){
        return st[1];
    }

    void debug(int id, int l, int r){
        cout << dbg(l) << dbg(r); st[id].debug();
        if(l < r){
            int mid = l + r >> 1;
            debug(id << 1, l, mid);
            debug(id << 1 | 1, mid + 1, r);
        }
    }
} chains[MAX];

void dfs_sz(int u){
    sz[u] = 1;
    for(int v : adj[u]){
        adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
        par[v] = u;
        dfs_sz(v);
        sz[u] += sz[v];
        if(sz[heavy[u]] < sz[v]) heavy[u] = v;
    }
}

void dfs_hld(int u, int hd){
    head[u] = hd;
    pos[u] = ++sz_chain[hd];
    if(heavy[u]){
        dfs_hld(heavy[u], hd);
        for(int v : adj[u]) if(v != heavy[u]){
            dfs_hld(v, v);
        }
    }
}

void initialize(int N, vector<int> A, vector<int> B){
    ::N = N;
    for(int i = 0; i < N - 1; ++i){
        int u = A[i], v = B[i];
        adj[u].emplace_back(v); adj[v].emplace_back(u);
    }

    dfs_sz(1);
    dfs_hld(1, 1);

    for(int i = 1; i <= N; ++i){
        if(head[i] == i){
            chains[i] = segment_tree(sz_chain[i]);
            chains[i].build(1, 1, sz_chain[i]);
        }
    }
}

void modify(int u, int cat, int dog){
    while(u > 0){
        node cur = chains[head[u]].get();
        int fcat = min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1});
        int fdog = min({cur.a[1][0], cur.a[1][1], cur.a[0][0] + 1, cur.a[0][1] + 1});

        chains[head[u]].update(1, 1, sz_chain[head[u]], pos[u], cat, dog);
        cur = chains[head[u]].get();

        int gcat = min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1});
        int gdog = min({cur.a[1][0], cur.a[1][1], cur.a[0][0] + 1, cur.a[0][1] + 1});

        cat = gcat - fcat;
        dog = gdog - fdog;
        u = par[head[u]];
    }
}

int answer(){
    node cur = chains[1].get();
    int cat = min(cur.a[0][0], cur.a[0][1]);
    int dog = min(cur.a[1][0], cur.a[1][1]);
    return min(cat, dog);
}

int cat(int u){
    modify(u, 0, MAX);
    t[u] = 1;
    return answer();
}

int dog(int u){
    modify(u, MAX, 0);
    t[u] = 2;
    return answer();
}

int neighbor(int u){
    if(t[u] == 1) modify(u, 0, -MAX);
    if(t[u] == 2) modify(u, -MAX, 0);
    t[u] = 0;
    return answer();
}

void test(){
    node a, b;
    a.a[0][0] = 0, a.a[1][1] = MAX, a.a[0][1] = MAX, a.a[1][0] = MAX;
    b.a[0][0] = MAX, b.a[1][1] = 0, b.a[0][1] = MAX, b.a[1][0] = MAX;

    node c = a + b;
    c.debug();
    exit(0);
}

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

    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);

//    test();
//    return 0;

    int N;
    cin >> N;
    vector<int> A(N - 1), B(N - 1);
    for(int i = 0; i < N - 1; ++i){
        cin >> A[i] >> B[i];
    }

    initialize(N, A, B);

    int Q; cin >> Q;
    while(Q--){
        int t, v;
        cin >> t >> v;
        if(t == 1) cout << cat(v) << '\n';
        if(t == 2) cout << dog(v) << '\n';
        if(t == 3) cout << neighbor(v) << '\n';
    }

    return 0;
}
#endif //LOCAL

Compilation message (stderr)

catdog.cpp: In member function 'void segment_tree::update(int, int, int, int, int, int)':
catdog.cpp:52:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |             int mid = l + r >> 1;
      |                       ~~^~~
catdog.cpp: In member function 'void segment_tree::build(int, int, int)':
catdog.cpp:66:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |             int mid = l + r >> 1;
      |                       ~~^~~
catdog.cpp: In member function 'void segment_tree::debug(int, int, int)':
catdog.cpp:80:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |             int mid = l + r >> 1;
      |                       ~~^~~

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