Submission #1188895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188895		alexdd	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	1 ms	2628 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;
    for(int i=0;i<n-1;i++)
    {
        con[A[i]].push_back(B[i]);
        con[B[i]].push_back(A[i]);
    }
    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)
    {
        //dp[nod][0] = min(dp[nod][0], dp[nod][1] + 1);
        //dp[nod][1] = min(dp[nod][1], dp[nod][0] + 1);
    }
    else if(a[nod]==0)
    {
        dp[nod][1] = dp[nod][0] + 1;
    }
    else if(a[nod]==1)
    {
        dp[nod][0] = dp[nod][1] + 1;
    }
    //cerr<<nod<<"  "<<dp[nod][0]<<" "<<dp[nod][1]<<" dp\n";
}

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]);
}
/*

5
1 2
2 3
2 4
4 5

2
1 3
2 5

*/

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