oj.uz

답안 #359865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
359865 2021-01-27T09:11:41 Z daniel920712 Cats or Dogs (JOI18_catdog) C++14
0 / 100
 3 ms 2668 KB 
#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]);
    }
}
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(3-color,i,here)+1);
    }
    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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -