Submission #939953

#TimeUsernameProblemLanguageResultExecution timeMemory
939953sleepntsheepCats or Dogs (JOI18_catdog)C++17
38 / 100
18 ms4188 KiB
#include "catdog.h" #include<stdio.h> #include<algorithm> #define N 2000 int shin[N],dp[N][2], e[N][2],ne,h[N]; void link(int u,int v) { e[++ne][0]=v,e[ne][1]=h[u],h[u]=ne; } void dfs(int u,int p) { dp[u][0]=dp[u][1]=0; for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])-p) { dfs(v,u); for(int k=0;k<2;++k) dp[u][k]+=std::min(dp[v][k],dp[v][k^1]+1); } if(shin[u]) { dp[u][(shin[u]-1)^1]=1e9; } } void initialize(int n, std::vector<int> a, std::vector<int> b) { for (int i=0;i<n-1;++i)link(a[i],b[i]),link(b[i],a[i]); } int cat(int u) { shin[u]=1; dfs(1,1); return std::min(dp[1][0],dp[1][1]); } int dog(int u) { shin[u]=2; dfs(1,1); return std::min(dp[1][0],dp[1][1]); } int neighbor(int u) { shin[u]=0; dfs(1,1); return std::min(dp[1][0],dp[1][1]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...