Submission #956146

#TimeUsernameProblemLanguageResultExecution timeMemory
956146caterpillowCats or Dogs (JOI18_catdog)C++17
38 / 100
3054 ms5728 KiB
#include <bits/stdc++.h> #include "catdog.h" using namespace std; using ll = long long; using pl = pair<ll, ll>; #define vt vector #define f first #define s second #define all(x) x.begin(), x.end() #define pb push_back #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define F0R(i, b) FOR (i, 0, b) #define endl '\n' #define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0) const ll INF = 1e18; int n; vt<vt<int>> adj; vt<int> state; pl dfs(int u, int par = -1) { ll cat = 0, dog = 0; for (int v : adj[u]) { if (v == par) continue; pl res = dfs(v, u); cat += res.f; dog += res.s; } pl res; if (state[u] == 1) dog = INF; if (state[u] == 2) cat = INF; res = {min(cat, dog + 1), min(cat + 1, dog)}; return res; } int solve() { pl res = dfs(0); return min(res.f, res.s); } void initialize(int N, vt<int> A, vt<int> B) { n = N; adj.resize(n); state.resize(n); F0R (i, n - 1) { adj[A[i] - 1].pb(B[i] - 1); adj[B[i] - 1].pb(A[i] - 1); } } int cat(int v) { v--; state[v] = 1; return solve(); } int dog(int v) { v--; state[v] = 2; return solve(); } int neighbor(int v) { v--; state[v] = 0; return solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...