Submission #102468

#	Time	Username	Problem	Language	Result	Execution time	Memory
102468		Dat160601	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3014 ms	8060 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int N = 1e5 + 7, inf = 1e9;

int n, par[N], head[N], chain[N], pos[N], sz[N], dp[N][2][2], st[N];
vector <int> edge[N];

void dfs(int u, int p){
	dp[u][0][0] = dp[u][0][1] = dp[u][1][0] = 0;
	if(st[u] == 1){
		dp[u][0][1] = inf;
		dp[u][0][0] = 1;
	}
	else if(st[u] == 2){
		dp[u][1][0] = inf;
		dp[u][0][0] = 1;
	}
	for(int v : edge[u]){
		if(v == p) continue;
		par[v] = u;
		dfs(v, u);
		dp[u][0][0] += min(dp[v][0][0], min(dp[v][1][0], dp[v][0][1]) + 1);
		dp[u][1][0] += min(dp[v][1][0], min(dp[v][0][0], dp[v][0][1] + 1));
		dp[u][0][1] += min(dp[v][0][1], min(dp[v][0][0], dp[v][1][0] + 1));
	}
}

void initialize(int p, vector<int> A, vector<int> B){
	n = p;
	for(int i = 0; i < n - 1; i++){
		edge[A[i]].pb(B[i]);
		edge[B[i]].pb(A[i]);
	}
	dfs(1, 1);
}

int getans(){
	return min(dp[1][0][0], min(dp[1][0][1], dp[1][1][0]));
}

int cat(int v) {
	st[v] = 1;
	dfs(1, 1);
	return getans();
}

int dog(int v) {
	st[v] = 2;
	dfs(1, 1);
	return getans();
}

int neighbor(int v) {
	st[v] = 0;
	dfs(1, 1);
	return getans();
}

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