Submission #359850

#	Time	Username	Problem	Language	Result	Execution time	Memory
359850		daniel920712	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	2 ms	2668 KiB

catdog

#include "catdog.h"
#include <vector>

using namespace std;

int x,now=1;
bool have1[1000005];
bool have2[1000005];
int vis[5][1000005];
int DP[5][1000005];
vector < int > Next[100005];
int color[1000005];
int N;
void initialize(int N, std::vector<int> A, std::vector<int> B)
{
    int i;
    ::N=N;
    for(i=1;i<N;i++)
    {
        Next[A[i]].push_back(B[i]);
        Next[B[i]].push_back(A[i]);
    }
}
void F2(int here,int fa)
{
    have1[here]=0;
    have2[here]=0;
    if(color[here]==1) have1[here]=1;
    if(color[here]==2) have2[here]=1;
    for(auto i:Next[here])
    {
        if(i==fa) continue;
        F2(i,here);
        have1[here]=have1[here]||have1[i];
        have2[here]=have2[here]||have2[i];
    }
}
int F(int color,int here,int fa)
{
    if(::color[here]!=color&&::color[here]) return 1e9;
    if(vis[color][here]==now) return DP[color][here];
    vis[color][here]=now;

    for(auto i:Next[here])
    {
        if(i==fa) continue;
        DP[color][here]+=min(F(color,i,here),F(2-color,i,here));
    }
    return DP[color][here];

}
int cat(int v)
{
    now++;
    color[v]=1;
    F2(1,-1);
    return min(F(1,1,-1),F(2,1,-1));
}

int dog(int v)
{
    now++;
    color[v]=2;
    F2(1,-1);
    return min(F(1,1,-1),F(2,1,-1));
}

int neighbor(int v)
{
    now++;
    color[v]=0;
    F2(1,-1);
    return min(F(1,1,-1),F(2,1,-1));
}

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