Submission #237856

#	Time	Username	Problem	Language	Result	Execution time	Memory
237856		Mercenary	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	232 ms	39152 KiB

catdog

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int sz[maxn];
int a[maxn];
int n , q;
vector<int> adj[maxn];
int chainhead[maxn];
int chainid[maxn];
int specid[maxn];
int par[maxn];


struct seg{
    struct node{
        int dp[2][2];
        node(){memset(dp,0,sizeof dp);};
        int getans(){
            int res = 1e5;
            for(int i = 0 ; i < 2 ; ++i)for(int j = 0 ; j < 2 ; ++j)res = min(res , dp[i][j]);
            return res;
        }
        friend node operator + (const node & a , const node & b){
            node res;
            for(int i = 0 ; i < 2 ; ++i)for(int j = 0 ; j < 2 ; ++j){
                res.dp[i][j] = 1e5;
                for(int k = 0 ; k < 2 ; ++k)for(int t = 0 ; t < 2 ; ++t){
                    res.dp[i][j] = min(res.dp[i][j] , a.dp[i][k] + b.dp[t][j] + (k ^ t));
                }
            }
            return res;
        }
    };
    vector<node> s;
    int n;
    void build(int x , int l , int r){
        if(l == r){
            s[x].dp[0][1] = s[x].dp[1][0] = 1e5;
            return;
        }
        int mid = l + r >> 1;
        build(x * 2 , l , mid);build(x * 2 + 1 , mid + 1 , r);
        s[x] = s[x * 2] + s[x * 2 + 1];
    }
    void init(){
        s.resize((n + 3) * 4);
        build(1,1,n);
    }
    void update(int x , int &pos , int &delta0 , int &delta1 , int l , int r){
        if(l == r){
            s[x].dp[0][0] += delta0;
            s[x].dp[1][1] += delta1;
            return;
        }
        int mid = l + r >> 1;
        if(pos <= mid)update(x * 2 , pos , delta0 , delta1 , l , mid);
        else update(x * 2 + 1, pos , delta0 , delta1 , mid + 1 , r);
        s[x] = s[x * 2] + s[x * 2 + 1];
    }
}s[maxn];

void update(int u , int delta0 , int delta1){
    while(u > 0){
        int curchain = chainid[u];
        auto pre = s[curchain].s[1];
        s[curchain].update(1,specid[u],delta0,delta1,1,s[curchain].n);
        auto now = s[curchain].s[1];
        delta0 = min({now.dp[0][0],now.dp[0][1],now.dp[1][0]+1,now.dp[1][1]+1})
            - min({pre.dp[0][0],pre.dp[0][1],pre.dp[1][0]+1,pre.dp[1][1]+1});
        delta1 = min({now.dp[0][0] + 1 ,now.dp[0][1] + 1 ,now.dp[1][0],now.dp[1][1]})
            - min({pre.dp[0][0] + 1 ,pre.dp[0][1] + 1 ,pre.dp[1][0],pre.dp[1][1]});
        u = par[chainhead[curchain]];
    }
}
void dfs(int u , int par){
    sz[u] = 1;
    for(auto c : adj[u]){
        if(c == par)continue;
        ::par[c] = u;
        dfs(c , u);
        sz[u] += sz[c];
    }
}

int nTime = 0;

void hld(int u , int par){
    ii best = mp(0,0);
    chainid[u] = nTime;
    specid[u] = ++s[nTime].n;
    if(chainhead[nTime] == 0)chainhead[nTime] = u;
    for(auto &c : adj[u]){
        if(c == par)continue;
        best = max(best,mp(sz[c],c));
    }
    if(best.second != 0)hld(best.second,u);
    for(auto &c : adj[u]){
        if(c == par || c == best.second)continue;
        ++nTime;
        hld(c , u);
    }
}

void initialize(int N, vector<int> A, vector<int> B) {
    n = N;
    for(int i = 0 ; i < n - 1 ; ++i){
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
    }
    for(int i = 1 ; i <= n ; ++i)a[i] = 3;
    dfs(1,0);
    hld(1,0);
    for(int i = 0 ; i <= nTime ; ++i){
        s[i].init();
    }
}

int cat(int v) {
    a[v] = 1;
    update(v,1e5,0);
    return s[0].s[1].getans();
}

int dog(int v) {
    a[v] = 2;
    update(v,0,1e5);
    return s[0].s[1].getans();
}

int neighbor(int v) {
    if(a[v] == 1)update(v,-1e5,0);
    else update(v,0,-1e5);
    return s[0].s[1].getans();
}

Compilation message (stderr)

catdog.cpp: In member function 'void seg::build(int, int, int)':
catdog.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
catdog.cpp: In member function 'void seg::update(int, int&, int&, int&, int, int)':
catdog.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~

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