Submission #937095

#TimeUsernameProblemLanguageResultExecution timeMemory
937095nguyentunglamCats or Dogs (JOI18_catdog)C++17
0 / 100
1 ms3676 KiB
#include<bits/stdc++.h> #define fi first #define se second #define endl "\n" #define ii pair<int, int> using namespace std; const int N = 1e5 + 10; int n; vector<int> adj[N]; int f[N], g[N], a[N]; void dfs(int u, int par) { f[u] = g[u] = 0; if (a[u] == 1) f[u] = 1e9; if (a[u] == 2) g[u] = 1e9; for(int &v : adj[u]) if (v != par) { dfs(v, u); f[u] += min(f[v], g[v] + 1); g[u] += min(g[v], f[u] + 1); } } void initialize (int N, vector<int> A, 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]); } } int cat(int v) { a[v] = 1; dfs(1, 0); return min(f[1], g[1]); } int dog(int v) { a[v] = 2; dfs(1, 0); return min(f[1], g[1]); } int neighbor(int v) { a[v] = 0; dfs(1, 0); return min(f[1], g[1]); } #ifdef ngu int main() { freopen ("task.inp", "r", stdin); freopen ("task.out", "w", stdout); int n; cin >> n; vector<int> a(n - 1), b(n - 1); for(int i = 0; i < n - 1; i++) cin >> a[i] >> b[i]; initialize(n, a, b); int q; cin >> q; while (q--) { int t, v; cin >> t >> v; if (t == 1) cout << cat(v); if (t == 2) cout << dog(v); if (t == 3) cout << neighbor(v); cout << endl; } } #endif // ngu
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...