Submission #894083

#TimeUsernameProblemLanguageResultExecution timeMemory
894083boxCats or Dogs (JOI18_catdog)C++17
0 / 100
1 ms2904 KiB
#include <bits/stdc++.h> using namespace std; #define ar array #define sz(v) int(std::size(v)) using i64 = long long; const int MAXN = 1e5; const int INF = 1e9; int N; vector<int> adj[MAXN]; int must[MAXN]; ar<int, 2> dfs(int p, int i) { ar<int, 2> c{0, 0}; for (int j : adj[i]) if (p != j) { auto v = dfs(i, j); c[0] += min(v[0], v[1] + 1); c[1] += min(v[0] + 1, v[1]); } if (must[i] & 1) c[0] = INF; if (must[i] & 2) c[1] = INF; return c; } int brute_dp() { auto v = dfs(-1, 0); return min(v[0], v[1]); } void initialize(int N, vector<int> A, vector<int> B) { for (int h = 0; h < N - 1; h++) { auto [i, j] = make_pair(A[h], B[h]); adj[i].push_back(j); adj[j].push_back(i); } } int cat(int i) { must[i] |= 1; return brute_dp(); } int dog(int i) { must[i] |= 2; return brute_dp(); } int neighbor(int i) { must[i] = 0; return brute_dp(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...