제출 #955458

#제출 시각아이디문제언어결과실행 시간메모리
955458Trisanu_DasCats or Dogs (JOI18_catdog)C++17
38 / 100
3006 ms7148 KiB
#include "catdog.h" #include <bits/stdc++.h> using namespace std; const int mxN=1e5, INF=1e9; int n, type[mxN], dp[mxN][2]; vector<int> adj[mxN]; void initialize(int N, vector<int> A, vector<int> B) { n=N; for (int i=0; i<n-1; ++i) { int u=A[i]-1, v=B[i]-1; adj[u].push_back(v); adj[v].push_back(u); } } void dfs(int u=0, int p=-1) { dp[u][0]=type[u]!=2?0:INF; dp[u][1]=type[u]!=1?0:INF; for (int v : adj[u]) if (v!=p) { dfs(v, u); for (int i : {0, 1}) dp[u][i]=min(min(dp[u][i]+dp[v][i], dp[u][i]+dp[v][i^1]+1), INF); } } int solve() { dfs(); return min(dp[0][0], dp[0][1]); } int cat(int v) { type[v-1]=1; return solve(); } int dog(int v) { type[v-1]=2; return solve(); } int neighbor(int v) { type[v-1]=0; return solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...