Submission #72624

#	Time	Username	Problem	Language	Result	Execution time	Memory
72624		ekrem	Cats or Dogs (JOI18_catdog)	C++98	38 / 100	3041 ms	60972 KiB

catdog

#include <bits/stdc++.h>
#include "catdog.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000007
#define N 1000005
using namespace std;

typedef vector < int > vi;

int a[N], dp[2][N];
vi gg[N], g[N];

int f(int node, int dur){
	int &r = dp[dur][node];
	if(r != -1)
		return r;
	r = 0;
	if(a[node] and a[node] - 1 != dur)
		return r = inf;
	for(int i = 0; i < g[node].size(); i++){
		int coc = g[node][i];
		r += min(f(coc, dur), f(coc, !dur) + 1);
	}
	// if(a[1] == 2)
	// 	cout << node << " " << dur << " -> " << r << endl;
	return r;
}

void hazirla(int node, int par){
	for(int i = 0; i < gg[node].size(); i++)
		if(gg[node][i] != par){
			g[node].pb(gg[node][i]);
			hazirla(gg[node][i], node);
		}
}

void initialize(int n, vi a, vi b){
	for(int i = 0; i < n - 1; i++){
		gg[a[i]].pb(b[i]);
		gg[b[i]].pb(a[i]);
	}
	hazirla(1, -1);
}

int cat(int v){
	memset(dp, -1, sizeof dp);
	a[v] = 1;
	return min(f(1, 0), f(1, 1));
}

int dog(int v){
	memset(dp, -1, sizeof dp);
	a[v] = 2;
	return min(f(1, 0), f(1, 1));
}

int neighbor(int v){
	memset(dp, -1, sizeof dp);
	a[v] = 0;
	return min(f(1, 0), f(1, 1));
}


// int main(){
// 	freopen("in.txt", "r", stdin);
// 	freopen("out.txt", "w", stdout);
// 	int n, q;
// 	scanf("%d",&n);
// 	vi a(n - 1), b(n - 1);
// 	for(int i = 0; i < n - 1; i++)
// 		scanf("%d %d",&a[i] ,&b[i]);
// 	scanf("%d",&q);
// 	vi t(q), v(q);
// 	for(int i = 0; i < q; i++)
// 		scanf("%d %d",&t[i] ,&v[i]);

// 	initialize(n, a, b);
// 	vi ans(q);
// 	for(int i = 0; i < q; i++){
// 		if(t[i] == 1)
// 			ans[i] = cat(v[i]);
// 		else if(t[i] == 2)
// 			ans[i] = dog(v[i]);
// 		else
// 			ans[i] = neighbor(v[i]);
// 	}
// 	for(int i = 0; i < q; i++)
// 		printf("%d\n",ans[i]);
// 	return 0;
// }

Compilation message (stderr)

catdog.cpp: In function 'int f(int, int)':
catdog.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
catdog.cpp: In function 'void hazirla(int, int)':
catdog.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < gg[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~

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