Submission #238461

#	Time	Username	Problem	Language	Result	Execution time	Memory
238461		DodgeBallMan	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	1843 ms	40172 KiB

catdog

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int INF = 1e9;

const int N = 1e5 + 10;
int n, par[N], rot[N], lev[N], col[N], sz[N], pos[N], dep[N];
pii pv[N];
vector<int> g[N];

struct node {
    vector<int> v;
    node() { 
        v = vector<int>( 4, INF );
        v[0] = v[3] = 0;
    }
    friend node operator+( const node &a, const node &b ) {
        node ret;
        ret.v = vector<int>( 4, INF );
        for( int i = 0 ; i < 4 ; i++ ) for( int j = 0 ; j < 4 ; j++ ) {
            int bit = ( i&2 ) + ( j&1 );
            int dif = ( i&1 ) != ( (j>>1)&1 );
            ret.v[bit] = min( ret.v[bit], a.v[i] + b.v[j] + dif );
        }
        return ret;
    }
}t[N*4];

node query( int ll, int rr, int l = 1, int r = n, int idx = 1 ) {
    if( l >= ll && r <= rr ) return t[idx];
    int mid = l + r >> 1;
    if( rr <= mid ) return query( ll, rr, l, mid, idx<<1 );
    else if( ll > mid ) return query( ll, rr, mid+1, r, idx<<1|1 );
    return query( ll, rr, l, mid, idx<<1 ) + query( ll, rr, mid+1, r, idx<<1|1 );
}

void update( int x, pii k, int l = 1, int r = n, int idx = 1 ) {
    if( l == r ) {
        t[idx].v[0] += k.x, t[idx].v[3] += k.y;
        return ;
    }
    int mid = l + r >> 1;
    if( x <= mid ) update( x, k, l, mid, idx<<1 );
    else update( x, k, mid+1, r, idx<<1|1 );
    t[idx] = t[idx<<1] + t[idx<<1|1];
}

void build( int l = 1, int r = n, int idx = 1 ) {
    if( l == r ) return ;
    int mid = l + r >> 1;
    build( l, mid, idx<<1 ), build( mid+1, r, idx<<1|1 );
    t[idx] = t[idx<<1] + t[idx<<1|1];
}

void updatehld( int u, pii now ) {
    while( u ) {
        //printf("%d %d\n",now.x,now.y);
        update( pos[u], now );
        //printf("U %d %d %d\n",u,pos[rot[u]],pos[lev[rot[u]]]);
        //node que2 = query( pos[u], pos[u] );
        node que = query( pos[rot[u]], pos[lev[rot[u]]] );
        //node que3 = query( pos[u], pos[lev[rot[u]]] );
        //node que4 = query( pos[lev[rot[u]]], pos[lev[rot[u]]] );
        //node que5 = que2 + que4;
        /*for( int i = 0 ; i < 4 ; i++ ) printf("%d ",que.v[i]);
        printf("\n");
        for( int i = 0 ; i < 4 ; i++ ) printf("%d ",que2.v[i]);
        printf("\n");
        for( int i = 0 ; i < 4 ; i++ ) printf("%d ",que3.v[i]);
        printf("\n");
        for( int i = 0 ; i < 4 ; i++ ) printf("%d ",que4.v[i]);
        printf("\n");
        for( int i = 0 ; i < 4 ; i++ ) printf("%d ",que5.v[i]);
        printf("\n");*/
        int x = min( que.v[0], que.v[1] ), y = min( que.v[2], que.v[3] );
        now = pii( min( x, y+1 ), min( x+1, y ) );
        //printf("%d %d\n",now.x,now.y);
        //printf("%d %d")
        pii temp = now;
        now.x = now.x - pv[rot[u]].x, now.y = now.y - pv[rot[u]].y;
        pv[rot[u]] = temp;
        u = par[rot[u]];
    }
    //printf("NO");
    return ;
}

void dfs( int u, int p ) {
    sz[u] = 1, par[u] = p, dep[u] = dep[p] + 1;
    if( p ) g[u].erase( find( g[u].begin(), g[u].end(), p ) );
    for( int &v : g[u] ) {
        dfs( v, u );
        sz[u] += sz[v];
        if( sz[v] > sz[g[u][0]] ) swap( v, g[u][0] );
    }
}

void hld( int u ) {
    static int idx = 0;
    if( !par[u] || u != g[par[u]][0] ) rot[u] = u;
    else rot[u] = rot[par[u]];
    lev[rot[u]] = u;
    pos[u] = ++idx;
    for( int v : g[u] ) hld( v );
} 

int cat( int u ) {
    col[u] = 1;
    updatehld( u, pii( 0, INF ) );
    //printf("U : %d",u);
    node ans = query( pos[rot[1]], pos[lev[1]] );
    int ret = INF;
    for( int i = 0 ; i < 4 ; i++ ) ret = min( ret, ans.v[i] );
    //printf("RET :%d\n",ret);
    return ret;
}

int dog( int u ) {
    col[u] = 2;
    updatehld( u, pii( INF, 0 ) );
    node ans = query( pos[rot[1]], pos[lev[1]] );
    int ret = INF;
    for( int i = 0 ; i < 4 ; i++ ) ret = min( ret, ans.v[i] );
    return ret;
}

int neighbor( int u ) {
    if( col[u] == 1 ) updatehld( u, pii( 0, -INF ) );
    else if( col[u] == 2 ) updatehld( u, pii( -INF, 0 ) );
    col[u] = 0;
    node ans = query( pos[rot[1]], pos[lev[1]] );
    int ret = INF;
    for( int i = 0 ; i < 4 ; i++ ) ret = min( ret, ans.v[i] );
    return ret;
}

void initialize( int _N, vector<int> A, vector<int> B ) {
    n = _N;
    for( int i = 0 ; i < n-1 ; i++ ) {
        g[A[i]].emplace_back( B[i] );
        g[B[i]].emplace_back( A[i] );
    }
    dfs( 1, 0 ), hld( 1 ), build();
}

/*int main()
{
    int n;
    vector<int> a, b;
    scanf("%d",&n);
    for( int i = 1, u, v ; i < n ; i++ ) {
        scanf("%d %d",&u,&v);
        a.emplace_back( u ), b.emplace_back( v );
    }
    initialize( n, a, b );
    while( 1 ) {
        int t, u;
        scanf("%d %d",&t,&u);
        //printf("WTF");
        if( t == 1 ) {
            printf("%d\n",cat( u ));
        }
        else if( t == 2 ) {
            printf("%d\n",dog( u ));
        }
        else {
            printf("%d\n",neighbor( u ));
        }
    }
    return 0;
}*/

Compilation message (stderr)

catdog.cpp: In function 'node query(int, int, int, int, int)':
catdog.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
catdog.cpp: In function 'void update(int, std::pair<int, int>, int, int, int)':
catdog.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
catdog.cpp: In function 'void build(int, int, int)':
catdog.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~

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