Submission #647907

#	Time	Username	Problem	Language	Result	Execution time	Memory
647907		khshg	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3058 ms	6044 KiB

catdog

#include<bits/stdc++.h>

using namespace std;

const int maxn = 100010, INF = 1e9;
int n;
vector<vector<int>> adj(maxn);
array<int, 2> dp[maxn];

void initialize(int _N, vector<int> A, vector<int> B) {
	n = _N;
	for(int i = 0; i < n - 1; ++i) {
		--A[i];
		--B[i];
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
}

bool oc[maxn][2];

void dfs(int s, int p) {
	dp[s][0] = dp[s][1] = 0;
	for(int& u : adj[s]) {
		if(u != p) {
			dfs(u, s);
			dp[s][0] += min(dp[u][0], dp[u][1] + 1);
			dp[s][1] += min(dp[u][1], dp[u][0] + 1);
		}
	}
	if(oc[s][0])
		dp[s][0] = INF;
	if(oc[s][1])
		dp[s][1] = INF;
}

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

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

int neighbor(int v) {
	--v;
	oc[v][0] = oc[v][1] = false;
	dfs(0, -1);
	return min(dp[0][0], dp[0][1]);
}
/*
int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}
 
int main(){
	int N=readInt();
	
	std::vector<int> A(N-1),B(N-1);
	for(int i=0;i<N-1;i++)
	{
		A[i]=readInt();
		B[i]=readInt();
	}
	int Q;
	assert(scanf("%d",&Q)==1);
	std::vector <int> T(Q),V(Q);
	for(int i=0;i<Q;i++)
	{
		T[i]=readInt();
		V[i]=readInt();
	}
	
	initialize(N,A,B);
	
	std::vector<int> res(Q);
	for(int j=0;j<Q;j++)
	{
		if(T[j]==1) res[j]=cat(V[j]);
		else if(T[j]==2) res[j]=dog(V[j]);
		else res[j]=neighbor(V[j]);
	}
	for(int j=0;j<Q;j++)
		printf("%d\n",res[j]);
	return 0;
}*/

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