Submission #1117328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117328		Hamed_Ghaffari	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	2 ms	2808 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>>1

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;
    for(int u=v; head[u]!=1; u=par[head[u]])
        upd(head[u], -1);
    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;
    for(int u=v; head[u]!=1; u=par[head[u]])
        upd(head[u], -1);
    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;
        for(int u=v; head[u]!=1; u=par[head[u]])
            upd(head[u], -1);
        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;
        for(int u=v; head[u]!=1; u=par[head[u]])
            upd(head[u], -1);
        Seg::upd(stt[v], Mp(-INF, 0));
        for(int u=v; head[u]!=1; u=par[head[u]])
            upd(head[u], 1);
    }
    return ans();
}

Compilation message (stderr)

catdog.cpp: In function 'void Seg::build(int, int, int)':
catdog.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 | #define mid l+r>>1
      |             ~^~
catdog.cpp:45:18: note: in expansion of macro 'mid'
   45 |         build(l, mid, lc);
      |                  ^~~
catdog.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 | #define mid l+r>>1
      |             ~^~
catdog.cpp:46:15: note: in expansion of macro 'mid'
   46 |         build(mid, r, rc);
      |               ^~~
catdog.cpp: In function 'void Seg::upd(int, pii, int, int, int)':
catdog.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 | #define mid l+r>>1
      |             ~^~
catdog.cpp:56:14: note: in expansion of macro 'mid'
   56 |         if(p<mid) upd(p, x, l, mid, lc);
      |              ^~~
catdog.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 | #define mid l+r>>1
      |             ~^~
catdog.cpp:56:32: note: in expansion of macro 'mid'
   56 |         if(p<mid) upd(p, x, l, mid, lc);
      |                                ^~~
catdog.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 | #define mid l+r>>1
      |             ~^~
catdog.cpp:57:24: note: in expansion of macro 'mid'
   57 |         else upd(p, x, mid, r, rc);
      |                        ^~~
catdog.cpp: In function 'node Seg::get(int, int, int, int, int)':
catdog.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 | #define mid l+r>>1
      |             ~^~
catdog.cpp:63:15: note: in expansion of macro 'mid'
   63 |         if(e<=mid) return get(s, e, l, mid, lc);
      |               ^~~
catdog.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 | #define mid l+r>>1
      |             ~^~
catdog.cpp:63:40: note: in expansion of macro 'mid'
   63 |         if(e<=mid) return get(s, e, l, mid, lc);
      |                                        ^~~
catdog.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 | #define mid l+r>>1
      |             ~^~
catdog.cpp:64:15: note: in expansion of macro 'mid'
   64 |         if(s>=mid) return get(s, e, mid, r, rc);
      |               ^~~
catdog.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 | #define mid l+r>>1
      |             ~^~
catdog.cpp:64:37: note: in expansion of macro 'mid'
   64 |         if(s>=mid) return get(s, e, mid, r, rc);
      |                                     ^~~
catdog.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 | #define mid l+r>>1
      |             ~^~
catdog.cpp:65:35: note: in expansion of macro 'mid'
   65 |         return merge(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
      |                                   ^~~
catdog.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 | #define mid l+r>>1
      |             ~^~
catdog.cpp:65:55: note: in expansion of macro 'mid'
   65 |         return merge(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
      |                                                       ^~~

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