Submission #1117333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117333		Hamed_Ghaffari	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	894 ms	23804 KiB

catdog

#include<bits/stdc++.h>
#include "catdog.h"

using namespace std;

using pii = pair<int, int>;

#define Mp make_pair
#define X first
#define Y second
#define pb push_back
#define mins(a,b) (a = min(a,b))
#define lc id<<1
#define rc lc|1
#define mid ((l+r)/2)

const int MXN = 1e5+5;
const int INF = 1e9;

int n;

struct node {int dp[2][2];} seg[MXN<<2];
node merge(node x, node y) {
    node res;
    for(int i : {0,1})
        for(int j : {0,1})
            res.dp[i][j] = INF;
    for(bool i : {0,1})
        for(bool j : {0,1})
            for(bool k : {0,1})
                for(bool l : {0,1})
                    mins(res.dp[i][l], x.dp[i][j]+y.dp[k][l]+(j!=k));
    return res;
}

namespace Seg {
    void build(int l=0, int r=n, int id=1) {
        if(r-l == 1) {
            seg[id].dp[0][0] = seg[id].dp[1][1] = 0;
            seg[id].dp[0][1] = seg[id].dp[1][0] = INF;
            return;
        }
        build(l, mid, lc);
        build(mid, r, rc);
        seg[id] = merge(seg[lc], seg[rc]);
    }

    void upd(int p, pii x, int l=0, int r=n, int id=1) {
        if(r-l==1) {
            seg[id].dp[0][0] += x.X;
            seg[id].dp[1][1] += x.Y;
            return;
        }
        if(p<mid) upd(p, x, l, mid, lc);
        else upd(p, x, mid, r, rc);
        seg[id] = merge(seg[lc], seg[rc]);
    }

    node get(int s, int e, int l=0, int r=n, int id=1) {
        if(s<=l && r<=e) return seg[id];
        if(e<=mid) return get(s, e, l, mid, lc);
        if(s>=mid) return get(s, e, mid, r, rc);
        return merge(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
    }
}

int sz[MXN], par[MXN], stt[MXN], fnt[MXN], head[MXN], timer;
bool is_cat[MXN], is_dog[MXN];
vector<int> g[MXN];

void dfs1(int v) {
    sz[v] = 1;
    for(int u : g[v])
        if(u^par[v]) {
            par[u] = v;
            dfs1(u);
            sz[v] += sz[u];
        }
}

void dfs2(int v) {
    if(!head[v]) head[v] = v;
    stt[v] = timer++;
    fnt[v] = timer;
    int big=-1;
    for(int u : g[v])
        if(u!=par[v] && (big==-1 || sz[big]<sz[u]))
            big = u;
    if(big != -1) {
        head[big] = head[v];
        dfs2(big);
        fnt[v] = fnt[big];
    }
    for(int u : g[v])
        if(u!=par[v] && u!=big)
            dfs2(u);
}

void upd(int v, int z) {
    v = head[v];
    if(v==1) return;
    node d = Seg::get(stt[v], fnt[v]);
    int C = min(d.dp[0][0], d.dp[0][1]);
    int D = min(d.dp[1][0], d.dp[1][1]);
    Seg::upd(stt[par[v]], Mp(z*min(C,D+1), z*min(C+1,D)));
}

int ans() {
    node d = Seg::get(stt[1], fnt[1]);
    return min({d.dp[0][0], d.dp[0][1], d.dp[1][0], d.dp[1][1]});
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n = N;
    for(int i=0; i<n-1; i++) g[A[i]].pb(B[i]), g[B[i]].pb(A[i]);
    dfs1(1);
    dfs2(1);
    Seg::build();
}

int cat(int v) {
    is_cat[v] = 1;
    vector<int> stk;
    for(int u=v; head[u]!=1; u=par[head[u]])
        stk.pb(head[u]);
    while(!stk.empty()) {
        upd(stk.back(), -1);
        stk.pop_back();
    }
    Seg::upd(stt[v], Mp(0, INF));
    for(int u=v; head[u]!=1; u=par[head[u]])
        upd(head[u], 1);
    return ans();
}

int dog(int v) {
    is_dog[v] = 1;
    vector<int> stk;
    for(int u=v; head[u]!=1; u=par[head[u]])
        stk.pb(head[u]);
    while(!stk.empty()) {
        upd(stk.back(), -1);
        stk.pop_back();
    }
    Seg::upd(stt[v], Mp(INF, 0));
    for(int u=v; head[u]!=1; u=par[head[u]])
        upd(head[u], 1);
    return ans();
}

int neighbor(int v) {
    if(is_cat[v]) {
        is_cat[v] = 0;
        vector<int> stk;
        for(int u=v; head[u]!=1; u=par[head[u]])
            stk.pb(head[u]);
        while(!stk.empty()) {
            upd(stk.back(), -1);
            stk.pop_back();
        }
        Seg::upd(stt[v], Mp(0, -INF));
        for(int u=v; head[u]!=1; u=par[head[u]])
            upd(head[u], 1);
    }
    if(is_dog[v]) {
        is_dog[v] = 0;
        vector<int> stk;
        for(int u=v; head[u]!=1; u=par[head[u]])
            stk.pb(head[u]);
        while(!stk.empty()) {
            upd(stk.back(), -1);
            stk.pop_back();
        }
        Seg::upd(stt[v], Mp(-INF, 0));
        for(int u=v; head[u]!=1; u=par[head[u]])
            upd(head[u], 1);
    }
    return ans();
}

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