제출 #359886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
359886		daniel920712	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3072 ms	7768 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=0;i<N-1;i++)
    {
        Next[A[i]].push_back(B[i]);
        Next[B[i]].push_back(A[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;
    DP[color][here]=0;
    for(auto i:Next[here])
    {
        if(i==fa) continue;
        DP[color][here]+=min(F(color,i,here),F(3-color,i,here)+1);
    }
    return DP[color][here];

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

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

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

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