Submission #70570

#	Time	Username	Problem	Language	Result	Execution time	Memory
70570		KLPP	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3007 ms	31664 KiB

catdog

#include "catdog.h"
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
typedef long long int lld;
int x;
vector<int> tree[1000000];
int animal[1000000];
int n;
void initialize(int N, std::vector<int> A, std::vector<int> B) {
	n=N;
	vector<int>nei[N];
	for(int i=0;i<N-1;i++){A[i]--;B[i]--;
		nei[A[i]].push_back(B[i]);
		nei[B[i]].push_back(A[i]);
	}
	queue<int>q;
	int dist[n];
	for(int i=0;i<n;i++){
		dist[i]=-1;
	}
	dist[0]=0;	
	q.push(0);
	dist[0]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<nei[u].size();i++){
			int v=nei[u][i];
			if(dist[v]==-1){
				dist[v]=dist[u]+1;
				q.push(v);
			}
		}
	}
	for(int i=0;i<n-1;i++){
		if(dist[A[i]]>dist[B[i]]){//cout<<B[i]<<" "<<A[i]<<endl;
			tree[B[i]].push_back(A[i]);
		}else{//cout<<A[i]<<" "<<B[i]<<endl;
			tree[A[i]].push_back(B[i]);
		}
	}
	for(int i=0;i<n;i++)animal[i]=0;
}

lld DP[1000000][3];

lld trabalha(int node,int territory){
	if(DP[node][territory]!=-1)return DP[node][territory];
	if(animal[node]>0 && territory!=animal[node])return 1000000000;
	if(tree[node].size()==0){
		DP[node][territory]=0;
		return 0;
	}
	DP[node][territory]=0;
	if(territory==1){
		for(int i=0;i<tree[node].size();i++){int v=tree[node][i];
			DP[node][territory]+=min(1+trabalha(v,0),min(trabalha(v,1),1+trabalha(v,2)));
		}
	}
	if(territory==2){
		for(int i=0;i<tree[node].size();i++){int v=tree[node][i];
			DP[node][territory]+=min(1+trabalha(v,0),min(trabalha(v,2),1+trabalha(v,1)));
		}
	}
	if(territory==0){
		for(int i=0;i<tree[node].size();i++){int v=tree[node][i];
			DP[node][territory]+=min(trabalha(v,0),min(1+trabalha(v,1),1+trabalha(v,2)));
		}
	}
	return DP[node][territory];
}
int cat(int v) {v--;
	animal[v]=1;
	for(int i=0;i<n;i++){
		DP[i][0]=-1;
		DP[i][1]=-1;
		DP[i][2]=-1;
	}
	//cout<<trabalha(0,1)<<endl;
	return min(trabalha(0,0),min(trabalha(0,1),trabalha(0,2)));
}

int dog(int v) {v--;
	animal[v]=2;
	for(int i=0;i<n;i++){
		DP[i][0]=-1;
		DP[i][1]=-1;
		DP[i][2]=-1;
	}
	return min(trabalha(0,0),min(trabalha(0,1),trabalha(0,2)));
}

int neighbor(int v){v--;
	animal[v]=0;
	for(int i=0;i<n;i++){
		DP[i][0]=-1;
		DP[i][1]=-1;
		DP[i][2]=-1;
	}
	return min(trabalha(0,0),min(trabalha(0,1),trabalha(0,2)));
}

Compilation message (stderr)

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<nei[u].size();i++){
               ~^~~~~~~~~~~~~~
catdog.cpp: In function 'lld trabalha(int, int)':
catdog.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<tree[node].size();i++){int v=tree[node][i];
               ~^~~~~~~~~~~~~~~~~~
catdog.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<tree[node].size();i++){int v=tree[node][i];
               ~^~~~~~~~~~~~~~~~~~
catdog.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<tree[node].size();i++){int v=tree[node][i];
               ~^~~~~~~~~~~~~~~~~~

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