Submission #122170

#	Time	Username	Problem	Language	Result	Execution time	Memory
122170		wilwxk	Cats or Dogs (JOI18_catdog)	C++11	38 / 100	3042 ms	7528 KiB

catdog

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

const int MAXN=1e5+5;
vector<int> g[MAXN];
int dp[MAXN][2];
int cor[MAXN];
int n;

void dfs(int cur, int p) {
	dp[cur][0]=dp[cur][1]=0;
	for(auto viz : g[cur]) {
		if(viz==p) continue;
		dfs(viz, cur);
		dp[cur][0]+=min(dp[viz][0], dp[viz][1]+1);
		dp[cur][1]+=min(dp[viz][1], dp[viz][0]+1);
	}
	if(cor[cur]!=-1) dp[cur][!cor[cur]]=n+n;
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
	n=N;
	for(int i=0; i<A.size(); i++) g[A[i]].push_back(B[i]), g[B[i]].push_back(A[i]);
	memset(cor, -1, sizeof(cor));
}

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

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

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

Compilation message (stderr)

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<A.size(); i++) g[A[i]].push_back(B[i]), g[B[i]].push_back(A[i]);
               ~^~~~~~~~~

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