#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))); }

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];
               ~^~~~~~~~~~~~~~~~~~