Submission #160262

#TimeUsernameProblemLanguageResultExecution timeMemory
160262iefnah06Cats or Dogs (JOI18_catdog)C++11
38 / 100
3036 ms7180 KiB
#include "catdog.h" #include<bits/stdc++.h> using namespace std; const int MAXN = 1.1e5; int N; vector<int> adj[MAXN]; int A[MAXN]; void initialize(int n, std::vector<int> a, std::vector<int> b) { N = n; for (int i = 0; i < N-1; i++) { adj[a[i]].push_back(b[i]); adj[b[i]].push_back(a[i]); } for (int i = 1; i <= N; i++) { A[i] = 2; } } int query(); int cat(int v) { A[v] = 0; return query(); } int dog(int v) { A[v] = 1; return query(); } int neighbor(int v) { A[v] = 2; return query(); } array<int, 2> dfs(int cur, int prv) { array<int, 2> best = {0,0}; for (int nxt : adj[cur]) { if (nxt == prv) continue; auto nxtbest = dfs(nxt, cur); for (int i = 0; i < 2; i++) best[i] += nxtbest[i]; } if (A[cur] == 2) { for (int i = 0; i < 2; i++) best[i] = min(best[i], 1 + best[1-i]); } else { best[1-A[cur]] = 1 + best[A[cur]]; } return best; } int query() { auto res = dfs(1, 0); return min(res[0], res[1]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...