Submission #468805

#	Time	Username	Problem	Language	Result	Execution time	Memory
468805		stefantaga	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3055 ms	10084 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,cats[200005],dogs[200005],tata[200005],niv[200005],nr,valoare[200005];
vector <int> gr[200005];
void dfs(int x,int t,int nivel)
{
    tata[x]=t;
    niv[x]=nivel;
    for (int i=0; i<gr[x].size(); i++)
    {
        int nod=gr[x][i];
        if (nod!=t)
        {
            dfs(nod,x,nivel+1);
        }
    }
}
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]);
    }
    for (i=1; i<=n; i++)
    {
        cats[i]=0;
        dogs[i]=0;
    }
    nr=0;
    dfs(1,0,1);
}
void solve(int x,int t)
{
    for (int i=0;i<gr[x].size();i++)
    {
        int nod=gr[x][i];
        if (nod!=t)
        {
            solve(nod,x);
        }
    }
    if (valoare[x]==1)
    {
        dogs[x]=INF;
    }
    else
    if (valoare[x]==2)
    {
        cats[x]=INF;
    }
    int i;
    for (i=0;i<gr[x].size();i++)
    {
        int nod=gr[x][i];
        if (nod!=t)
        {
            dogs[x]+=min(dogs[nod],cats[nod]+1);
            cats[x]+=min(cats[nod],dogs[nod]+1);
        }
    }
}
int calculeaza()
{
    int i;
    for (i=1;i<=n2;i++)
    {
        cats[i]=dogs[i]=0;
    }
    solve(1,0);
    if (valoare[1]==1)
    {
        return cats[1];
    }
    if (valoare[1]==2)
    {
        return dogs[1];
    }
    return min(dogs[1],cats[1]);
}
int cat(int v)
{
    valoare[v]=1;
    return calculeaza();
}

int dog(int v)
{
    valoare[v]=2;
    return calculeaza();
}

int neighbor(int v)
{
    valoare[v]=0;
    return calculeaza();
}








/*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:16:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i=0; i<gr[x].size(); i++)
      |                   ~^~~~~~~~~~~~~
catdog.cpp: In function 'void solve(int, int)':
catdog.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i=0;i<gr[x].size();i++)
      |                  ~^~~~~~~~~~~~~
catdog.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (i=0;i<gr[x].size();i++)
      |              ~^~~~~~~~~~~~~

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