Submission #1112899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112899		12345678	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	902 ms	26092 KiB

catdog

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

using namespace std;

const int nx=1e5+5, inf=1e9;

int n, pa[nx], hd[nx], hv[nx], in[nx], out[nx], t, sz[nx], type[nx];
vector<int> d[nx];

struct segtree
{
    struct node
    {
        int dp[2][2];
        node() {dp[0][1]=dp[1][0]=inf, dp[0][0]=dp[1][1]=0;}
        friend node operator+ (const node &lhs, const node &rhs)
        {
            node tmp;
            tmp.dp[0][0]=tmp.dp[0][1]=tmp.dp[1][0]=tmp.dp[1][1]=inf;
            for (int i=0; i<2; i++) for (int j=0; j<2; j++) for (int k=0; k<2; k++) for (int l=0; l<2; l++) tmp.dp[i][j]=min(tmp.dp[i][j], lhs.dp[i][k]+rhs.dp[l][j]+(k!=l));
            return tmp;
        }
    } d[4*nx];
    void update(int l, int r, int i, int idx, int x, int y)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i].dp[0][0]+=x, d[i].dp[1][1]+=y, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, x, y);
        update(md+1, r, 2*i+1, idx, x, y);
        d[i]=d[2*i]+d[2*i+1];
    }
    node query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return node();
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
    pair<int, int> getrange(int u)
    {
        node tmp=query(1, n, 1, in[u], out[u]);
        int cat=min(tmp.dp[0][0], tmp.dp[0][1]), dog=min(tmp.dp[1][0], tmp.dp[1][1]);
        return {min(cat, dog+1), min(cat+1, dog)};
    }
} s;

void dfssz(int u, int p)
{
    sz[u]=1;
    pa[u]=p;
    for (auto v:d[u]) if (v!=p) dfssz(v, u), sz[u]+=sz[v], hv[u]=(sz[hv[u]]>sz[v])?hv[u]:v;
}

void hld(int u, int p, int g)
{
    hd[u]=g;
    in[u]=++t;
    out[g]=t;
    if (hv[u]) hld(hv[u], u, g);
    for (auto v:d[u]) if (v!=p&&v!=hv[u]) hld(v, u, v);
}

void update(int u, int x, int y)
{
    while (1)
    {
        //cout<<"debug "<<u<<' '<<hd[u]<<'\n';
        auto prev=s.getrange(hd[u]);
        //cout<<"euler "<<in[hd[u]]<<' '<<out[hd[u]]<<'\n';
        //cout<<"prev "<<prev.first<<' '<<prev.second<<'\n';
        s.update(1, n, 1, in[u], x, y);
        auto cur=s.getrange(hd[u]);
        //cout<<"after "<<cur.first<<' '<<cur.second<<'\n';
        x=cur.first-prev.first, y=cur.second-prev.second;
        if (pa[hd[u]]==-1) break;
        u=pa[hd[u]];
    }
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n=N;
    for (int i=0; i<n-1; i++) d[A[i]].push_back(B[i]), d[B[i]].push_back(A[i]);
    dfssz(1, -1);
    //for (int i=1; i<=n; i++) cout<<"here "<<i<<' '<<hv[i]<<' '<<pa[i]<<'\n'; 
    hld(1, 1, 1);
    //for (int i=1; i<=n; i++) cout<<"hd "<<i<<' '<<hd[i]<<'\n';
}

int cat(int v) {
    type[v]=1;
    update(v, 0, inf);
    auto res=s.getrange(1);
    return min(res.first, res.second);
}

int dog(int v) {
    type[v]=2;
    update(v, inf, 0);
    auto res=s.getrange(1);
    return min(res.first, res.second);
}

int neighbor(int v) {
    if (type[v]==1) update(v, 0, -inf);
    else update(v, -inf, 0);
    auto res=s.getrange(1);
    return min(res.first, res.second);
}

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