Submission #151893

#	Time	Username	Problem	Language	Result	Execution time	Memory
151893		arnold518	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	12 ms	9080 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];

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 update(int node, int tl, int tr, int pos, int val)
    {
        if(tl==tr)
        {
            if(val==0) tree[node]=Node(0, 0, 0, 0);
            if(val==1) tree[node]=Node(1, INF, INF, INF);
            if(val==2) tree[node]=Node(INF, INF, INF, 1);
            return;
        }
        if(tr<pos || pos<tl) 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]);
    }

    Node query(int node, int tl, int tr, int l, int r)
    {
        if(l<=tl && tr<=r) return tree[node];
        if(r<tl || tr<l) return Node();
        int mid=tl+tr>>1;
        return combine(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
    }
}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) 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);
    }
}

int query(int u)
{
    Node ret;
    while(u)
    {
        ret=combine(seg.query(1, 1, N, idx[head[u]], idx[u]), ret);
        u=par[head[u]];
    }
    return min({ret.AA, ret.AB, ret.BA, ret.BB});
}

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);
}

int cat(int u)
{
    seg.update(1, 1, N, idx[u], 1);
    return query(u);
}

int dog(int u)
{
    seg.update(1, 1, N, idx[u], 2);
    return query(u);
}

int neighbor(int u)
{
    seg.update(1, 1, N, idx[u], 0);
    return query(u);
}

Compilation message (stderr)

catdog.cpp: In member function 'void SEG::update(int, int, int, int, int)':
catdog.cpp:49:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In member function 'Node SEG::query(int, int, int, int, int)':
catdog.cpp:59: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:114:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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