Submission #1054257

#TimeUsernameProblemLanguageResultExecution timeMemory
1054257NeroZeinCats or Dogs (JOI18_catdog)C++17
0 / 100
0 ms348 KiB
#include "bits/stdc++.h" using namespace std; #ifdef Nero #include "Deb.h" #else #define debug(...) #endif const int N = 1003; int n; int a[N]; int pr[N]; int cats[N]; int dogs[N]; int dp[N][2]; vector<int> g[N]; void dfs(int v, int p) { for (int u : g[v]) { if (u != p) { pr[u] = v; dfs(u, v); } } } void initialize(int n_, vector<int> A, vector<int> B) { n = n_; for (int i = 0; i < n - 1; ++i) { g[A[i]].push_back(B[i]); g[B[i]].push_back(A[i]); } dfs(1, 1); } int cat(int v) { a[v] = 1; cats[v]++; bool f = false; while (v != 1) { v = pr[v]; if (!f) { dp[v][1]++; } f |= cats[v] > 0; cats[v]++; } int ret = 0; for (int i = 1; i <= n; ++i) { if (a[v] == 0) { ret = max(ret, min(dp[i][0], dp[i][1])); } else if (a[v] == 1) { ret = max(ret, dp[i][0]); } else { ret = max(ret, dp[i][1]); } } return ret; } int dog(int v) { a[v] = 2; dogs[v]++; bool f = false; while (v != 1) { v = pr[v]; if (!f) { dp[v][0]++; } f |= dogs[v] > 0; dogs[v]++; } int ret = 0; for (int i = 1; i <= n; ++i) { if (a[v] == 0) { ret = max(ret, min(dp[i][0], dp[i][1])); } else if (a[v] == 1) { ret = max(ret, dp[i][0]); } else { ret = max(ret, dp[i][1]); } } return ret; } int neighbor(int v) { if (a[v] == 1) { cats[v]--; bool f = false; while (v != 1) { v = pr[v]; if (!f) { dp[v][1]--; } f |= cats[v] > 0; cats[v]--; } } else { dogs[v]--; bool f = false; while (v != 1) { v = pr[v]; if (!f) { dp[v][0]--; } f |= dogs[v] > 0; dogs[v]--; } } a[v] = 0; int ret = 0; for (int i = 1; i <= n; ++i) { if (a[v] == 0) { ret = max(ret, min(dp[i][0], dp[i][1])); } else if (a[v] == 1) { ret = max(ret, dp[i][0]); } else { ret = max(ret, dp[i][1]); } } return ret; } //int main() { //ios::sync_with_stdio(false); //cin.tie(nullptr); //int n; //cin >> n; //vector<int> A(n), B(n); //for (int i = 0; i < n - 1; ++i) { //cin >> A[i] >> B[i]; //} //initialize(n, A, B); //int q; //cin >> q; //while(q--) { //int type, v; //cin >> type >> v; //int ans = 0; //if (type == 1) { //ans = cat(v); //} else if (type == 2) { //ans = dog(v); //} else { //ans = neighbor(v); //} //cout << ans << '\n'; //} //return 0; //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...