이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |