Submission #64671

#	Time	Username	Problem	Language	Result	Execution time	Memory
64671		zscoder	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3051 ms	8768 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int N = 111111;
int n;
vi adj[N];
int alien[N];
int dp[N][3];

const int INF = int(1e9);
void dfs(int u, int p=-1)
{
	dp[u][0]=dp[u][1]=dp[u][2]=INF;
	if(alien[u]==0) dp[u][0]=0;
	if(alien[u]==0||alien[u]==1) dp[u][1]=0;
	if(alien[u]==0||alien[u]==2) dp[u][2]=0;
	for(int v:adj[u])
	{
		if(v==p) continue;
		dfs(v,u);
		if(alien[u]==0)
		{
			dp[u][0]+=min(dp[v][0],min(dp[v][1]+1,dp[v][2]+1));
		}
		if(alien[u]==0||alien[u]==1)
		{
			dp[u][1]+=min(dp[v][0],min(dp[v][1],dp[v][2]+1));
		}
		if(alien[u]==0||alien[u]==2)
		{
			dp[u][2]+=min(dp[v][0],min(dp[v][1]+1,dp[v][2]));
		}
	}
}

void initialize(int N, std::vector<int> A, std::vector<int> B) 
{
	n=N;
	for(int i=0;i<N-1;i++) 
	{
		adj[A[i]-1].pb(B[i]-1); adj[B[i]-1].pb(A[i]-1);
	}
	dfs(0);
	memset(alien,0,sizeof(alien));
}

int cat(int v) 
{
	v--; alien[v]=1;
	dfs(0);
	return min(dp[0][0],min(dp[0][1],dp[0][2]));
}

int dog(int v) 
{
	v--; alien[v]=2;
	dfs(0);
	return min(dp[0][0],min(dp[0][1],dp[0][2]));
}

int neighbor(int v) 
{
	v--; alien[v]=0;
	dfs(0);
	return min(dp[0][0],min(dp[0][1],dp[0][2]));
}

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