Submission #367870

#	Time	Username	Problem	Language	Result	Execution time	Memory
367870		denkendoemeer	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	304 ms	22636 KiB

catdog

#include<bits/stdc++.h>
#include "catdog.h"
#define ll long long
using namespace std;
const int inf=1e9;
int min(int a,int b)
{
    if (a<b)
        return a;
    return b;
}
struct mat
{
    int a[2][2];
    void init()
    {
        a[0][0]=a[1][1]=0;
        a[1][0]=a[0][1]=inf;
    }
    mat()
    {
        init();
    }
    mat operator * (mat b) const
    {
        mat c;
        int i,j,k,e;
        for(i=0;i<2;i++)
            for(j=0;j<2;j++){
                c.a[i][j]=inf;
                for(k=0;k<2;k++)
                    for(e=0;e<2;e++)
                        c.a[i][j]=min(c.a[i][j],a[i][k]+b.a[e][j]+(k^e));
            }
        return c;
    }
}aint[200005];
int l[200005],r[200005],root[100005],u;
void update(int &nod,int st,int dr,int poz,int a,int b)
{
    if (nod==0)
        nod=++u;
    if (st==dr){
        aint[nod].a[0][0]+=a;
        aint[nod].a[1][1]+=b;
        return ;
    }
    int mij=(st+dr)/2;
    if (poz<=mij)
        update(l[nod],st,mij,poz,a,b);
    else
        update(r[nod],mij+1,dr,poz,a,b);
    aint[nod]=aint[l[nod]]*aint[r[nod]];
}
pair<int,int> query(int nod)
{
    int a=min(aint[nod].a[0][0],aint[nod].a[0][1]),b=min(aint[nod].a[1][0],aint[nod].a[1][1]);
    a=min(a,b+1);
    b=min(b,a+1);
    return make_pair(a,b);
}
int head[100005],sz[100005],dep[100005],t[100005],sz2[100005];
vector<int>g[100005];
void dfs(int nod,int tat)
{
    t[nod]=tat;
    dep[nod]=dep[tat]+1;
    sz[nod]=1;
    for(auto it:g[nod])
        if (it!=tat)
            dfs(it,nod),sz[nod]+=sz[it];
}
void hld(int nod,int tat)
{
    if (head[nod]==0)
        head[nod]=nod;
    sz2[head[nod]]++;
    int ok=0;
    for(auto it:g[nod])
        if (it!=tat && sz[ok]<sz[it])
            ok=it;
    if (ok)
        head[ok]=head[nod];
    for(auto it:g[nod])
        if (it!=tat)
            hld(it,nod);
}
int nr[100005];
void initialize(int n,vector<int>a,vector<int>b)
{
    int i;
    for(i=0;i<n-1;i++)
        g[a[i]].push_back(b[i]),g[b[i]].push_back(a[i]);
    dfs(1,0);
    hld(1,0);
}
int calc()
{
    pair<int,int>aux=query(root[1]);
    return min(aux.first,aux.second);
}
void mark(int nod,int a,int b)
{
    while(nod){
        int xa,xb,ya,yb;
        pair<int,int>aux=query(root[head[nod]]);
        xa=aux.first;
        xb=aux.second;
        update(root[head[nod]],1,sz2[head[nod]],dep[nod]-dep[head[nod]]+1,a,b);
        aux=query(root[head[nod]]);
        ya=aux.first;
        yb=aux.second;
        a=ya-xa;
        b=yb-xb;
        nod=t[head[nod]];
    }
}
int cat(int nod)
{
    nr[nod]=1;
    mark(nod,100000,0);
    return calc();
}
int dog(int nod)
{
    nr[nod]=2;
    mark(nod,0,100000);
    return calc();
}
int neighbor(int nod)
{
    if (nr[nod]==1)
        mark(nod,-100000,0);
    if (nr[nod]==2)
        mark(nod,0,-100000);
    return calc();
}

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