Submission #669161

#TimeUsernameProblemLanguageResultExecution timeMemory
669161tibinyteCats or Dogs (JOI18_catdog)C++14
0 / 100
0 ms212 KiB
#include <bits/stdc++.h> #include "catdog.h" using namespace std; const int inf = 1e9; vector<int> a; vector<vector<int>> g; vector<vector<int>> dp; void initialize(int N, vector<int> A, vector<int> B) { g = vector<vector<int>>(N + 1); dp = vector<vector<int>>(N + 1, vector<int>(2)); a = vector<int>(N + 1, 2); for (int i = 1; i <= N; ++i) { g[A[i]].emplace_back(B[i]); g[B[i]].emplace_back(A[i]); } } void dfs(int node, int parent) { for (int i = 0; i < 2; ++i) { dp[node][i] = 0; } bool leaf = true; for (auto i : g[node]) { if (i != parent) { dfs(i, node); for (int j = 0; j < 2; ++j) { dp[node][j] += min(dp[i][j], dp[i][j ^ 1] + 1); } leaf = false; } } if (a[node] != 2) { dp[node][a[node] ^ 1] = inf; } } int cat(int v) { a[v] = 0; dfs(1, 0); return min(dp[1][0], dp[1][1]); } int dog(int v) { a[v] = 1; dfs(1, 0); return min(dp[1][0], dp[1][1]); } int neighbor(int v) { a[v] = 2; dfs(1, 0); return min(dp[1][0], dp[1][1]); }

Compilation message (stderr)

catdog.cpp: In function 'void dfs(int, int)':
catdog.cpp:25:10: warning: variable 'leaf' set but not used [-Wunused-but-set-variable]
   25 |     bool leaf = true;
      |          ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...