제출 #134047

#제출 시각아이디문제언어결과실행 시간메모리
134047osaaateiasavtnlCats or Dogs (JOI18_catdog)C++14
100 / 100
1113 ms26012 KiB
#include<bits/stdc++.h> using namespace std; #define app push_back const int N = 1e5 + 7; const int INF = 1e9 + 7; struct Dp { int a[2][2]; Dp () { for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { a[i][j] = INF; } } } int* operator[](int i) { return a[i]; } Dp operator *(Dp add) { Dp ans; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { for (int ii = 0; ii < 2; ++ii) { for (int jj = 0; jj < 2; ++jj) { ans[i][jj] = min(ans[i][jj], a[i][j] + add[ii][jj] + (j ^ ii)); } } } } return ans; } }; int cnt[N], to[N]; vector <int> g[N]; void dfs1(int u, int p) { cnt[u] = 1; int mx = -1; for (int v : g[u]) { if (v != p) { dfs1(v, u); cnt[u] += cnt[v]; if (mx == -1 || cnt[mx] < cnt[v]) mx = v; } } if (mx == -1) { to[u] = u; return; } int pos = -1; for (int i = 0; i < g[u].size(); ++i) { if (g[u][i] == mx) pos = i; } swap(g[u][0], g[u][pos]); to[u] = to[mx]; } int up[N], pos[N], par[N], ptr = 0; void dfs2(int u, int p) { par[u] = p; pos[u] = ptr++; for (int v : g[u]) { if (v != p) { if (v == g[u][0]) up[v] = up[u]; else up[v] = v; dfs2(v, u); } } } Dp tree[N << 2]; Dp EM; Dp get(int v, int tl, int tr, int l, int r) { if (tr < l || r < tl) return EM; if (l <= tl && tr <= r) return tree[v]; int tm = (tl + tr) >> 1; return get(v * 2 + 1, tl, tm, l, r) * get(v * 2 + 2, tm + 1, tr, l, r); } void relax(int v) { tree[v] = tree[v * 2 + 1] * tree[v * 2 + 2]; } void build(int v, int tl, int tr) { if (tl == tr) { tree[v] = EM; return; } int tm = (tl + tr) >> 1; build(v * 2 + 1, tl, tm); build(v * 2 + 2, tm + 1, tr); relax(v); } void upd(int v, int tl, int tr, int p, int d0, int d1) { if (tl == tr) { tree[v][0][0] += d0; tree[v][1][1] += d1; return; } int tm = (tl + tr) >> 1; if (p <= tm) upd(v * 2 + 1, tl, tm, p, d0, d1); else upd(v * 2 + 2, tm + 1, tr, p, d0, d1); relax(v); } void initialize(int n, vector <int> a, vector <int> b) { EM[0][0] = EM[1][1] = 0; for (int i = 0; i < n - 1; ++i) { g[a[i]].app(b[i]); g[b[i]].app(a[i]); } up[1] = 1; dfs1(1, 0); dfs2(1, 0); build(0, 0, N); } pair <int, int> get_dp(int v) { auto m = get(0, 0, N, pos[v], pos[to[v]]); int dp0 = min(m[0][0], m[0][1]), dp1 = min(m[1][0], m[1][1]); return {min(dp0, dp1 + 1), min(dp0 + 1, dp1)}; } int get() { auto m = get(0, 0, N, pos[1], pos[to[1]]); int dp0 = min(m[0][0], m[0][1]), dp1 = min(m[1][0], m[1][1]); return min(dp0, dp1); } void anime(int v, int d0, int d1) { while (v) { int f0, f1, s0, s1; tie(f0, f1) = get_dp(up[v]); upd(0, 0, N, pos[v], d0, d1); tie(s0, s1) = get_dp(up[v]); d0 = s0 - f0; d1 = s1 - f1; v = par[up[v]]; } } bool type[N]; int cat(int v) { type[v] = 0; anime(v, 0, INF); return get(); } int dog(int v) { type[v] = 1; anime(v, INF, 0); return get(); } int neighbor(int v) { if (type[v]) anime(v, -INF, 0); else anime(v, 0, -INF); return get(); } #ifdef HOME signed main() { freopen("input.txt", "r", stdin); int n, q; cin >> n >> q; vector <int> a, b; for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; a.push_back(u); b.push_back(v); } initialize(n, a, b); for (int i = 0; i < q; ++i) { int t, v; cin >> t >> v; if (t == 1) cout << cat(v) << '\n'; else if (t == 2) cout << dog(v) << '\n'; else cout << neighbor(v) << '\n'; } } #endif /* 5 3 1 2 1 4 2 3 2 4 1 3 2 5 2 4 */

컴파일 시 표준 에러 (stderr) 메시지

catdog.cpp: In function 'void dfs1(int, int)':
catdog.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[u].size(); ++i) {
                     ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...