Submission #468842

#	Time	Username	Problem	Language	Result	Execution time	Memory
468842		stefantaga	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	307 ms	65340 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#include <cstdio>
#include <cassert>
#include <vector>
#include <stdlib.h>
#define INF 100000005
using namespace std;

int x,tata[200005],niv[200005],nr,valoare[200005],mar[200005],max_fiu[200005];
vector <int> gr[200005];
void dfs(int x,int t,int nivel)
{
    tata[x]=t;
    niv[x]=nivel;
    mar[x]=1;
    for (int i=0; i<gr[x].size(); i++)
    {
        int nod=gr[x][i];
        if (nod!=t)
        {
            dfs(nod,x,nivel+1);
            mar[x]+=mar[nod];
            if (mar[nod]>mar[max_fiu[x]])
            {
                max_fiu[x]=nod;
            }
        }
    }
}struct Nod
    {
        long long cost[2][2];
    };
class SegmentTree
{
    Nod *arb;
public:
    void inline Initeaza(int nr)
    {
        arb = new Nod [((nr<<4)+1)];
        for (int i=1;i<=(nr<<2);i++)
        {
            arb[i].cost[0][0]=arb[i].cost[1][1]=0;
            arb[i].cost[1][0]=arb[i].cost[0][1]=0;
        }
    }
    void inline update(int st,int dr,int nod,int poz, Nod val)
    {
        int a,b,c,d;
        if (st==dr)
        {
            arb[nod]=val;
            return;
        }
        int mij=(st+dr)/2;
        if (poz<=mij)
        {
            update(st,mij,2*nod,poz,val);
        }
        else
        {
            update(mij+1,dr,2*nod+1,poz,val);
        }
        for (a=0;a<=1;a++)
        {
            for (b=0;b<=1;b++)
            {
                arb[nod].cost[a][b]=INF;
            }
        }
        for (a=0;a<=1;a++)
        {
            for (b=0;b<=1;b++)
            {
                for (c=0;c<=1;c++)
                {
                    for (d=0;d<=1;d++)
                    {
                        arb[nod].cost[a][d]=min(arb[nod].cost[a][d],arb[2*nod].cost[a][b]+arb[2*nod+1].cost[c][d]+(b^c));
                    }
                }
            }
        }
    }
    void add(int st,int dr,int nod,int poz,int val1,int val2)
    {
        int a,b,c,d;
        if (st==dr)
        {
            arb[nod].cost[0][0]+=val1;
            arb[nod].cost[1][1]+=val2;
            return;
        }
        int mij=(st+dr)/2;
        if (poz<=mij)
        {
            add(st,mij,2*nod,poz,val1,val2);
        }
        else
        {
            add(mij+1,dr,2*nod+1,poz,val1,val2);
        }
        for (a=0;a<=1;a++)
        {
            for (b=0;b<=1;b++)
            {
                arb[nod].cost[a][b]=INF;
            }
        }
        for (a=0;a<=1;a++)
        {
            for (b=0;b<=1;b++)
            {
                for (c=0;c<=1;c++)
                {
                    for (d=0;d<=1;d++)
                    {
                        arb[nod].cost[a][d]=min(arb[nod].cost[a][d],arb[2*nod].cost[a][b]+arb[2*nod+1].cost[c][d]+(b^c));
                    }
                }
            }
        }
    }
    pair <int,int>  get()
    {
        int a,b,v0,v1;
        a=min(arb[1].cost[0][0],arb[1].cost[0][1]);
        b=min(arb[1].cost[1][0],arb[1].cost[1][1]);
        v0=min(a,b+1);
        v1=min(b,a+1);
        return {v0,v1};
    }
}*chains;
int id[200005],cnt[200005],q,primul[200005],poz[200005];
void split (int x,int t)
{
    id[x]=q;
    cnt[q]++;
    poz[x]=cnt[q];
    if (primul[q]==0)
    {
        primul[q]=x;
    }
    if (max_fiu[x]==0)
    {
        return;
    }
    split(max_fiu[x],x);
    for (int i=0;i<gr[x].size();i++)
    {
        int nod=gr[x][i];
        if (nod!=t&&nod!=max_fiu[x])
        {
            q++;
            split(nod,x);
        }
    }
}
int n2;
void initialize(int n, std::vector<int> A, std::vector<int> B)
{
    n2=n;
    int i;
    for (i=0; i<n-1; i++)
    {
        gr[A[i]].push_back(B[i]);
        gr[B[i]].push_back(A[i]);
    }
    nr=0;
    dfs(1,0,1);
    q=1;
    split(1,0);
    chains = new SegmentTree [(q+1)];
    for (i=1;i<=q;i++)
    {
        chains[i].Initeaza(cnt[i]);
    }
    Nod valint;
    valint.cost[0][0]=valint.cost[1][1]=0;
    valint.cost[0][1]=valint.cost[1][0]=INF;
    for (i=1;i<=n;i++)
    {
        chains[id[i]].update(1,cnt[id[i]],1,poz[i],valint);
    }
}
pair <int,int> salut;
void update(int x,int v0,int v1)
{
    while (x)
    {
        pair <int,int> inainte,acum;
        inainte=chains[id[x]].get();
        chains[id[x]].add(1,cnt[id[x]],1,poz[x],v0,v1);
        acum=chains[id[x]].get();
        v0=acum.first-inainte.first;
        v1=acum.second-inainte.second;
        x=tata[primul[id[x]]];
    }
}
int cat(int v)
{
    valoare[v]=1;
    update(v,0,INF);
    salut=chains[1].get();
    return min(salut.first,salut.second);
}

int dog(int v)
{
    valoare[v]=2;
    update(v,INF,0);
    salut=chains[1].get();
    return min(salut.first,salut.second);
}

int neighbor(int v)
{
    if (valoare[v]==1)
    {
        update(v,0,-INF);
        salut=chains[1].get();
        valoare[v]=0;
        return min(salut.first,salut.second);
    }
    else
    if (valoare[v]==2)
    {
        update(v,-INF,0);
        salut=chains[1].get();
        valoare[v]=0;
        return min(salut.first,salut.second);
    }
    return 0;
}








/*int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}

int main(){
	int N=readInt();

	std::vector<int> A(N-1),B(N-1);
	for(int i=0;i<N-1;i++)
	{
		A[i]=readInt();
		B[i]=readInt();
	}
	int Q;
	assert(scanf("%d",&Q)==1);
	std::vector <int> T(Q),V(Q);
	for(int i=0;i<Q;i++)
	{
		T[i]=readInt();
		V[i]=readInt();
	}

	initialize(N,A,B);

	std::vector<int> res(Q);
	for(int j=0;j<Q;j++)
	{
		if(T[j]==1) res[j]=cat(V[j]);
		else if(T[j]==2) res[j]=dog(V[j]);
		else res[j]=neighbor(V[j]);
	}
	for(int j=0;j<Q;j++)
		printf("%d\n",res[j]);
	return 0;
}*/

Compilation message (stderr)

catdog.cpp: In function 'void dfs(int, int, int)':
catdog.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i=0; i<gr[x].size(); i++)
      |                   ~^~~~~~~~~~~~~
catdog.cpp: In function 'void split(int, int)':
catdog.cpp:149:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for (int i=0;i<gr[x].size();i++)
      |                  ~^~~~~~~~~~~~~

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