제출 #978180

#제출 시각아이디문제언어결과실행 시간메모리
978180vjudge1Cats or Dogs (JOI18_catdog)C++17
100 / 100
405 ms28244 KiB
// #include "catdog.h" #include <bits/stdc++.h> using namespace std; const int inf = 100000; int n, m, u, v, add[2], sub[2], color[100005], f[100005][2], _g[100005][2]; int cnt, fa[100005], siz[100005], dep[100005], son[100005], dfn[100005], top[100005], rnk[100005], bot[100005]; vector<int> e[100005]; struct matrix { int v[2][2]; matrix(int val = inf) { v[0][0] = val, v[0][1] = inf; v[1][0] = inf, v[1][1] = val; } matrix operator = (const matrix& _) { v[0][0] = _.v[0][0], v[0][1] = _.v[0][1]; v[1][0] = _.v[1][0], v[1][1] = _.v[1][1]; return *this; } matrix operator * (const matrix& _) const { matrix ret; ret.v[0][0] = min(v[0][0] + _.v[0][0], v[0][1] + _.v[1][0]); ret.v[0][1] = min(v[0][0] + _.v[0][1], v[0][1] + _.v[1][1]); ret.v[1][0] = min(v[1][0] + _.v[0][0], v[1][1] + _.v[1][0]); ret.v[1][1] = min(v[1][0] + _.v[0][1], v[1][1] + _.v[1][1]); return ret;//循环展开后的广义矩阵乘法 } } ans, before, after, g[100005]; struct Segment_Tree {//线段树维护转移矩阵 matrix val[400005]; int pos, L, R, l[400005], r[400005]; #define lc (k << 1) #define rc ((k << 1) | 1) #define mid ((l[k] + r[k]) >> 1) void push_up(int k) { val[k] = val[lc] * val[rc]; } void build(int k) { if(l[k] == r[k]) { val[k] = g[rnk[l[k]]]; return; } l[lc] = l[k], r[lc] = mid, l[rc] = mid + 1, r[rc] = r[k]; build(lc), build(rc); push_up(k); } void change(int k) { if(l[k] == r[k]) { val[k] = g[rnk[pos]]; return; } if(pos <= mid) change(lc); else change(rc); push_up(k); } matrix ask(int k) { if(L <= l[k] && r[k] <= R) return val[k]; matrix ret(0); if(L <= mid) ret = ret * ask(lc); if(R > mid) ret = ret * ask(rc); return ret; } void Change(int Pos) { pos = Pos; return change(1); } matrix Ask(int l, int r) { L = l, R = r; return ask(1); } } tree; //树链剖分 void dfs1(int now) { siz[now] = 1, dep[now] = dep[fa[now]] + 1; for(const auto& i : e[now]) { if(i != fa[now]) { fa[i] = now; dfs1(i); siz[now] += siz[i]; if(siz[i] > siz[son[now]]) son[now] = i; } } } void dfs2(int now) { ++cnt; dfn[now] = cnt, rnk[cnt] = now; if(now == son[fa[now]]) top[now] = top[fa[now]]; else top[now] = now; if(son[now]) { dfs2(son[now]); bot[now] = bot[son[now]]; f[now][0] += min(f[son[now]][0], f[son[now]][1] + 1); f[now][1] += min(f[son[now]][0] + 1, f[son[now]][1]); } else bot[now] = now; for(const auto& i : e[now]) { if(i != fa[now] && i != son[now]) { dfs2(i); f[now][0] += min(f[i][0], f[i][1] + 1); f[now][1] += min(f[i][0] + 1, f[i][1]); _g[now][0] += min(f[i][0], f[i][1] + 1); _g[now][1] += min(f[i][0] + 1, f[i][1]); } } g[now].v[0][0] = _g[now][0], g[now].v[0][1] = _g[now][0] + 1; g[now].v[1][0] = _g[now][1] + 1, g[now].v[1][1] = _g[now][1]; } //修改转移矩阵 void change(int now, int val) { g[now].v[0][0] = _g[now][0], g[now].v[0][1] = _g[now][0] + 1; g[now].v[1][0] = _g[now][1] + 1, g[now].v[1][1] = _g[now][1]; color[now] = val; if(color[now]) g[now].v[color[now] - 1][0] = g[now].v[color[now] - 1][1] = inf;//把不可能出现的一行设为inf while(now) { before = tree.Ask(dfn[top[now]], dfn[bot[now]]); tree.Change(dfn[now]); after = tree.Ask(dfn[top[now]], dfn[bot[now]]); now = fa[top[now]]; add[0] = min(after.v[0][0], after.v[0][1]), sub[0] = min(before.v[0][0], before.v[0][1]); add[1] = min(after.v[1][0], after.v[1][1]), sub[1] = min(before.v[1][0], before.v[1][1]); _g[now][0] += min(add[0], add[1] + 1) - min(sub[0], sub[1] + 1), _g[now][1] += min(add[0] + 1, add[1]) - min(sub[0] + 1, sub[1]); g[now].v[0][0] = _g[now][0], g[now].v[0][1] = _g[now][0] + 1; g[now].v[1][0] = _g[now][1] + 1, g[now].v[1][1] = _g[now][1]; if(color[now]) g[now].v[color[now] - 1][0] = g[now].v[color[now] - 1][1] = inf;//不可能出现的状态 } } //下面就是交互了 void initialize(int N, std::vector<int> A, std::vector<int> B) { n = N; for(int i = 2; i <= n; ++i) { u = A[i - 2], v = B[i - 2]; e[u].push_back(v); e[v].push_back(u); } dfs1(1); dfs2(1); tree.l[1] = 1, tree.r[1] = n; tree.build(1); } int cat(int v) { change(v, 1); ans = tree.Ask(dfn[top[1]], dfn[bot[1]]); return min(min(ans.v[0][0], ans.v[0][1]), min(ans.v[1][0], ans.v[1][1])); } int dog(int v) { change(v, 2); ans = tree.Ask(dfn[top[1]], dfn[bot[1]]); return min(min(ans.v[0][0], ans.v[0][1]), min(ans.v[1][0], ans.v[1][1])); } int neighbor(int v) { change(v, 0); ans = tree.Ask(dfn[top[1]], dfn[bot[1]]); return min(min(ans.v[0][0], ans.v[0][1]), min(ans.v[1][0], ans.v[1][1])); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...