Submission #894063

#TimeUsernameProblemLanguageResultExecution timeMemory
894063vovikCats or Dogs (JOI18_catdog)C++17
38 / 100
3022 ms7876 KiB
#include <bits/stdc++.h> void initialize(int N, std::vector<int> A, std::vector<int> B); int cat(int v); int dog(int v); int neighbor(int v); std::vector<int> g[100005]; int dp[100005][2]; int tp[100005]; void initialize(int N, std::vector<int> A, std::vector<int> B) { for (int i = 0; i < A.size(); ++i) g[A[i]].push_back(B[i]), g[B[i]].push_back(A[i]); } void dfs(int v, int p = -1) { int s0 = 0, s1 = 0; for (auto u: g[v]) { if (u == p) continue; dfs(u, v), s0 += dp[u][0], s1 += dp[u][1]; } if (!tp[v]) dp[v][0] = std::min(s0, s1 + 1), dp[v][1] = std::min(s1, s0 + 1); else if (tp[v] == 1) dp[v][1] = (dp[v][0] = s0) + 1; else dp[v][0] = (dp[v][1] = s1) + 1; } int cat(int v) { return tp[v] = 1, dfs(1), std::min(dp[1][0], dp[1][1]); } int dog(int v) { return tp[v] = 2, dfs(1), std::min(dp[1][0], dp[1][1]); } int neighbor(int v) { return tp[v] = 0, dfs(1), std::min(dp[1][0], dp[1][1]); } #ifdef __APPLE__ #include <cstdio> #include <cassert> #include <vector> #include <cstdlib> int readInt() { int i; if (scanf("%d", &i) != 1) { fprintf(stderr, "Error while reading input\n"); exit(1); } return i; } int main() { int N = readInt(); std::vector<int> A(N - 1), B(N - 1); for (int i = 0; i < N - 1; i++) { A[i] = readInt(); B[i] = readInt(); } int Q; assert(scanf("%d",&Q)==1); std::vector<int> T(Q), V(Q); for (int i = 0; i < Q; i++) { T[i] = readInt(); V[i] = readInt(); } initialize(N, A, B); std::vector<int> res(Q); for (int j = 0; j < Q; j++) { if (T[j] == 1) res[j] = cat(V[j]); else if (T[j] == 2) res[j] = dog(V[j]); else res[j] = neighbor(V[j]); } for (int j = 0; j < Q; j++) printf("%d\n", res[j]); return 0; } #endif

Compilation message (stderr)

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < A.size(); ++i) g[A[i]].push_back(B[i]), g[B[i]].push_back(A[i]);
      |                     ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...