Submission #1188879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188879		alexdd	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	1 ms	2624 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e5;
int n;
int a[100005];
vector<int> con[100005];
int parent[100005];
int dp[100005][2];
void dfs(int nod)
{
    for(int adj:con[nod])
    {
        if(adj==parent[nod])
            continue;
        parent[adj] = nod;
        dfs(adj);
    }
}
void initialize(int N, std::vector<int> A, std::vector<int> B)
{
    n=N;
    for(int i=1;i<=N;i++)
        a[i]=2;
    dfs(1);
}

void calcdp(int nod)
{
    dp[nod][0] = dp[nod][1] = 0;
    for(int adj:con[nod])
    {
        if(adj==parent[nod])
            continue;
        calcdp(adj);
        dp[nod][0] += dp[adj][0];
        dp[nod][1] += dp[adj][1];
    }
    if(a[nod]==2)
    {

    }
    else if(a[nod]==0)
    {
        dp[nod][1] = INF;
    }
    else if(a[nod]==1)
    {
        dp[nod][0] = INF;
    }
}

int cat(int v)
{
    a[v] = 0;
    calcdp(1);
    return min(dp[1][0], dp[1][1]);
}

int dog(int v)
{
    a[v] = 1;
    calcdp(1);
    return min(dp[1][0], dp[1][1]);
}

int neighbor(int v)
{
    a[v] = 2;
    calcdp(1);
    return min(dp[1][0], dp[1][1]);
}

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