Submission #883949

#TimeUsernameProblemLanguageResultExecution timeMemory
883949vjudge1Cats or Dogs (JOI18_catdog)C++17
0 / 100
1 ms3932 KiB
#include "catdog.h" #include<bits/stdc++.h> using namespace std; int n; vector<int> con[100005]; int dp[100005][3]; int tip[100005]; void dfs(int nod, int par) { if(tip[nod]==0) { dp[nod][0]=0; dp[nod][1]=0; dp[nod][2]=0; } else if(tip[nod]==1) { dp[nod][0]=1; dp[nod][1]=0; dp[nod][2]=1; } else { dp[nod][0]=1; dp[nod][1]=1; dp[nod][2]=0; } for(auto adj:con[nod]) { if(adj!=par) { dfs(adj,nod); dp[nod][0] += min({dp[adj][0],dp[adj][1]+1,dp[adj][2]+1}); dp[nod][1] += min({dp[adj][0],dp[adj][1],dp[adj][2]+1}); dp[nod][2] += min({dp[adj][0],dp[adj][1]+1,dp[adj][2]}); } } } void initialize(int N, std::vector<int> A, std::vector<int> B) { n=N; for(int i=0;i<n-1;i++) { con[A[i]].push_back(B[i]); con[B[i]].push_back(A[i]); } } int cat(int v) { tip[v]=1; dfs(1,0); return min({dp[1][0],dp[1][1],dp[1][2]}); } int dog(int v) { tip[v]=2; dfs(1,0); return min({dp[1][0],dp[1][1],dp[1][2]}); } int neighbor(int v) { tip[v]=0; dfs(1,0); return min({dp[1][0],dp[1][1],dp[1][2]}); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...