Submission #330516

#TimeUsernameProblemLanguageResultExecution timeMemory
330516BeanZCats or Dogs (JOI18_catdog)C++14
38 / 100
3098 ms7256 KiB
// I_Love_LPL #include <bits/stdc++.h> using namespace std; #define ll int #define endl '\n' const int N = 1e5 + 5; const int lg = 60; const int mod = 998244353; const long long oo = 1e18; const int lim = 1e6 + 5; long double eps = 1e-3; vector<ll> node[N]; ll dpc[N], dpd[N], color[N]; void initialize(ll n, vector<ll> A, vector<ll> B){ for (int i = 1; i < n; i++){ node[A[i - 1]].push_back(B[i - 1]); node[B[i - 1]].push_back(A[i - 1]); } } void dfs(ll u, ll p){ dpc[u] = 0; dpd[u] = 0; if (color[u] == 1) dpd[u] = 1e9; if (color[u] == 2) dpc[u] = 1e9; for (auto j : node[u]){ if (j == p) continue; dfs(j, u); if (color[u] == 1) dpc[u] += min(dpc[j], dpd[j] + 1); else if (color[u] == 2) dpd[u] += min(dpd[j], dpc[j] + 1); else dpc[u] += min(dpc[j], dpd[j] + 1), dpd[u] += min(dpd[j], dpc[j] + 1); } } ll Solve(){ dfs(1, 1); return min(dpc[1], dpd[1]); } ll cat(ll v){ color[v] = 1; return Solve(); } ll dog(ll v){ color[v] = 2; return Solve(); } ll neighbor(ll v){ color[v] = 0; return Solve(); } /* int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("A.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll n; cin >> n; vector<ll> A, B; for (int i = 1; i < n; i++){ ll u, v; cin >> u >> v; A.push_back(u); B.push_back(v); } initialize(n, A, B); ll q; cin >> q; while (q--){ ll task; cin >> task; if (task == 0){ ll u; cin >> u; cout << neighbor(u) << endl; } else if (task == 1){ ll u; cin >> u; cout << cat(u) << endl; } else { ll u; cin >> u; cout << dog(u) << endl; } } } /* 5 1 2 2 3 2 4 4 5 5 1 3 2 5 1 2 2 1 0 2 */

Compilation message (stderr)

catdog.cpp:87:1: warning: "/*" within comment [-Wcomment]
   87 | /*
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...