Submission #883991

#TimeUsernameProblemLanguageResultExecution timeMemory
883991vjudge1Cats or Dogs (JOI18_catdog)C++17
38 / 100
3026 ms12356 KiB
#include "catdog.h" #include<bits/stdc++.h> using namespace std; const int INF = 1e9; int n; vector<int> con[100005]; int dp[100005][3]; int tip[100005]; int parent[100005]; void calcdp(int nod) { dp[nod][0]=0; dp[nod][1]=0; dp[nod][2]=0; for(auto adj:con[nod]) { if(adj!=parent[nod]) { if(tip[nod]==0) { 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]}); } else if(tip[nod]==1) { dp[nod][0] += min({dp[adj][0],dp[adj][1],dp[adj][2]+1}); dp[nod][1] += min({dp[adj][0],dp[adj][1],dp[adj][2]+1}); } else { dp[nod][0] += min({dp[adj][0],dp[adj][1]+1,dp[adj][2]}); dp[nod][2] += min({dp[adj][0],dp[adj][1]+1,dp[adj][2]}); } } } if(tip[nod]==0) { } else if(tip[nod]==1) { dp[nod][0]++; dp[nod][2]=INF; } else { dp[nod][0]++; dp[nod][1]=INF; } } void dfs(int nod, int par) { parent[nod]=par; for(auto adj:con[nod]) if(adj!=par) dfs(adj,nod); calcdp(nod); } 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]); } dfs(1,0); } int cat(int v) { tip[v]=1; int cur=v; while(cur!=0) { calcdp(cur); cur=parent[cur]; } return min({dp[1][0],dp[1][1],dp[1][2]}); } int dog(int v) { tip[v]=2; int cur=v; while(cur!=0) { calcdp(cur); cur=parent[cur]; } return min({dp[1][0],dp[1][1],dp[1][2]}); } int neighbor(int v) { tip[v]=0; int cur=v; while(cur!=0) { calcdp(cur); cur=parent[cur]; } return min({dp[1][0],dp[1][1],dp[1][2]}); } /** 5 1 2 2 3 2 4 4 5 5 1 3 2 5 1 2 2 1 3 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...