Submission #152104

#	Time	Username	Problem	Language	Result	Execution time	Memory
152104		arnold518	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	10 ms	8952 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int INF = 1e6;

int N;
vector<int> adj[MAXN+10];

int sz[MAXN+10], par[MAXN+10], dep[MAXN+10];
int idx[MAXN+10], cnt=1, head[MAXN+10], tail[MAXN+10];

struct Node
{
    int AA, AB, BA, BB;
    Node(int AA, int AB, int BA, int BB) : AA(AA), AB(AB), BA(BA), BB(BB) {}
    Node() : AA(0), AB(0), BA(0), BB(0) {}
};

Node combine(Node lc, Node rc)
{
    Node ret;
    ret.AA=min({lc.AA+rc.AA, lc.AA+rc.BA+1, lc.AB+rc.AA+1, lc.AB+rc.BA});
    ret.AB=min({lc.AA+rc.AB, lc.AA+rc.BB+1, lc.AB+rc.AB+1, lc.AB+rc.BB});
    ret.BA=min({lc.BA+rc.AA, lc.BA+rc.BA+1, lc.BB+rc.AA+1, lc.BB+rc.BA});
    ret.BB=min({lc.BA+rc.AB, lc.BA+rc.BB+1, lc.BB+rc.AB+1, lc.BB+rc.BB});
    return ret;
}

struct SEG
{
    Node tree[MAXN*4+10];

    void init(int node, int tl, int tr)
    {
        if(tl==tr) { tree[node]=Node(0, INF, INF, 0); return; }
        int mid=tl+tr>>1;
        init(node*2, tl, mid);
        init(node*2+1, mid+1, tr);
    }

    void update(int node, int tl, int tr, int pos, Node val)
    {
        if(tr<pos || pos<tl) return;
        if(tl==tr)
        {
            tree[node]=val;
            return;
        }
        int mid=tl+tr>>1;
        update(node*2, tl, mid, pos, val);
        update(node*2+1, mid+1, tr, pos, val);
        tree[node]=combine(tree[node*2], tree[node*2+1]);
    }

    void query(int node, int tl, int tr, int l, int r, vector<Node> &ret)
    {
        if(l<=tl && tr<=r) { ret.push_back(tree[node]); return; }
        if(r<tl || tr<l) return;
        int mid=tl+tr>>1;
        query(node*2, tl, mid, l, r, ret);
        query(node*2+1, mid+1, tr, l, r, ret);
    }

    Node query(int l, int r)
    {
        int i, j;
        vector<Node> V;
        query(1, 1, N, l, r, V);
        Node ret=V[0];
        for(i=1; i<V.size(); i++) ret=combine(ret, V[i]);
        return ret;
    }

    void debug(int node, int tl, int tr)
    {
        printf("%d %d %d : %d %d %d %d\n", node, tl, tr, tree[node].AA, tree[node].AB, tree[node].BA, tree[node].BB);
        if(tl==tr) return;
        int mid=tl+tr>>1;
        debug(node*2, tl, mid);
        debug(node*2+1, mid+1, tr);
    }
}seg;

void dfs(int now, int bef, int depth)
{
    sz[now]=1;
    par[now]=bef;
    dep[now]=depth;
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        dfs(nxt, now, depth+1);
        sz[now]+=sz[nxt];
    }
}

void hld(int now, int bef)
{
    idx[now]=cnt++;

    int heavy=0;
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        if(sz[heavy]<sz[nxt]) heavy=nxt;
    }

    if(heavy==0)
    {
        tail[now]=now;
        return;
    }

    head[heavy]=head[now];
    hld(heavy, now);

    for(int nxt : adj[now])
    {
        if(nxt==bef || nxt==heavy) continue;
        head[nxt]=nxt;
        hld(nxt, now);
    }

    tail[now]=tail[heavy];
}

void initialize(int _N, vector<int> A, vector<int> B)
{
    int i, j;
    N=_N;

    for(i=0; i<N-1; i++)
    {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }

    dfs(1, 0, 1);
    head[1]=1;
    hld(1, 0);
    seg.init(1, 1, N);
}

int query(int u, int val)
{
    Node chg;
    if(val==0) chg=Node(0, 0, 0, 0);
    if(val==1) chg=Node(0, INF, INF, INF);
    if(val==2) chg=Node(INF, INF, INF, 0);

    while(head[u]!=1)
    {
        int a=par[head[u]], b=head[u];
        Node qa=seg.query(idx[a], idx[a]), qb=seg.query(idx[head[b]], idx[tail[b]]);
        qa.AA-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
        qa.BB-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
        seg.update(1, 1, N, idx[u], chg);
        qb=seg.query(idx[head[b]], idx[tail[b]]);
        qa.AA+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
        qa.BB+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));

        chg=qa;
        u=par[head[u]];
    }

    seg.update(1, 1, N, idx[u], chg);
    Node ans=seg.query(idx[head[1]], idx[tail[1]]);

    return min({ans.AA, ans.AB, ans.BA, ans.BB});
}

int cat(int u)
{
    return query(u, 1);
}

int dog(int u)
{
    return query(u, 2);
}

int neighbor(int u)
{
    return query(u, 0);
}

Compilation message (stderr)

catdog.cpp: In member function 'void SEG::init(int, int, int)':
catdog.cpp:42:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In member function 'void SEG::update(int, int, int, int, Node)':
catdog.cpp:55:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In member function 'void SEG::query(int, int, int, int, int, std::vector<Node>&)':
catdog.cpp:65:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In member function 'Node SEG::query(int, int)':
catdog.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=1; i<V.size(); i++) ret=combine(ret, V[i]);
                  ~^~~~~~~~~
catdog.cpp:72:16: warning: unused variable 'j' [-Wunused-variable]
         int i, j;
                ^
catdog.cpp: In member function 'void SEG::debug(int, int, int)':
catdog.cpp:84:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:135:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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