| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1122819 | FucKanh | Cats or Dogs (JOI18_catdog) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 2;
const int inf = 1e7;
int n,state[maxn],sz[maxn],par[maxn];
int root[maxn], pos[maxn],cnt[maxn];
int dp[maxn][3];
int sumC[maxn], sumD[maxn];
vector<int> a[maxn];
void dfs(int u, int pa = -1) {
sz[u] = 1;
for (int i = 0; i < a[u].size(); i++) {
int v = a[u][i];
if (pa == v) continue;
par[v] = u;
dfs(v,u);
sz[u] += sz[v];
if (sz[v] >= sz[a[u][0]] || a[u][0] == pa) swap(a[u][0], a[u][i]);
}
}
void hld(int u, int pa = -1) {
if (a[u][0] == pa) return;
root[a[u][0]] = root[u];
pos[a[u][0]] = pos[u] + 1;
hld(a[u][0], u);
cnt[root[u]]++;
for (int i = 1; i < a[u].size(); i++) {
int v = a[u][i];
if (pa == v) continue;
root[a[u][i]] = a[u][i];
pos[a[u][i]] = 1;
cnt[a[u][i]] = 1;
hld(a[u][i], u);
}
}
class IT {
vector<array<int,4>> t;
int n;
public:
void build(int v, int l, int r) {
if (l==r) {
t[v][0] = inf;
t[v][1] = inf;
t[v][2] = t[v][3] = 0;
return;
}
int mid = l + r >> 1;
build(v*2,l,mid);
build(v*2+1,mid+1,r);
t[v] = merged(t[v*2],t[v*2+1]);
}
void init(int N) {
n = N;
t.resize((n+1)*4,array<int,4>());
build(1,1,n);
}
/*
re[0] = cd
re[1] = dc
re[2] = cc
re[3] = dd
*/
array<int,4> merged(array<int,4> a, array<int,4> b) {
array<int,4> re;
if (b[0]==-inf) return a;
if (a[0]==-inf) return b;
re[0] = min({a[2] + b[0], a[0] + b[3], a[0] + b[0] + 1, a[2] + b[3] + 1});
re[1] = min({a[3] + b[1], a[1] + b[2], a[3] + b[2] + 1, a[1] + b[1] + 1});
re[2] = min({a[2] + b[2], a[0] + b[1], a[2] + b[1] + 1, a[0] + b[2] + 1});
re[3] = min({a[3] + b[3], a[1] + b[0], a[3] + b[0] + 1, a[1] + b[3] + 1});
return re;
}
void update(int v, int l, int r,int pos, int d, int c) {
if (l==r) {
t[v][0] = t[v][1] = inf;
t[v][2] = c;
t[v][3] = d;
// cerr << "update node: " << v << " " << l << " " << r << " : " << t[v][0] << " " << t[v][1] << " " << t[v][2] << " " << t[v][3] << endl;
return;
}
int mid = l + r >> 1;
if (pos <= mid) update(v*2,l,mid,pos,d,c);
else update(v*2+1,mid+1,r,pos,d,c);
t[v] = merged(t[v*2],t[v*2+1]);
// cerr << "update: " << v << " " << l << " " << r << " : " << t[v][0] << " " << t[v][1] << " " << t[v][2] << " " << t[v][3] << endl;
// cerr << "FROM: " << t[v*2][0] << " " << t[v*2][1] << " " << t[v*2][2] << " " << t[v*2][3] << endl;
// cerr << "FROM: " << t[v*2+1][0] << " " << t[v*2+1][1] << " " << t[v*2+1][2] << " " << t[v*2+1][3] << endl;
}
array<int,4> get(int v, int l, int r, int L, int R) {
if (L > R) return array<int,4>({-inf,-inf,-inf,-inf});
if (L == l && R == r) return t[v];
int mid = l + r >> 1;
return merged(get(v*2,l,mid,L,min(R,mid)), get(v*2+1,mid+1,r,max(mid+1,L),R));
}
};
IT tree[maxn];
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
for (int i = 0; i < N-1; i++) {
a[A[i]].push_back(B[i]);
a[B[i]].push_back(A[i]);
}
root[1] = 1;
cnt[1] = 1;
pos[1] = 1;
dfs(1);
hld(1);
for (int i = 1; i <= n; i++) {
if (root[i] == i) tree[i].init(cnt[i]);
}
}
void query(int v) {
array<int,4> pre,now;
while (v) {
// cerr << v << " - " << root[v] << " " << pos[v] << endl;
pre = tree[root[v]].get(1,1,cnt[root[v]],1,cnt[root[v]]);
if (state[v] == 1) tree[root[v]].update(1,1,cnt[root[v]],pos[v],inf,sumC[v]);
else if (state[v] == 2) tree[root[v]].update(1,1,cnt[root[v]],pos[v],sumD[v],inf);
else tree[root[v]].update(1,1,cnt[root[v]],pos[v],sumD[v],sumC[v]);
// cerr << "nxt " << root[v] << endl;
now = tree[root[v]].get(1,1,cnt[root[v]],1,cnt[root[v]]);
v = root[v];
if (par[v] == 0) {
// cerr << "Done" << endl;
return;
}
// cerr << "Change sum: " << par[v] << " : " << min({now[1], now[2], now[0] + 1, now[3] + 1}) - min({pre[1], pre[2],pre[0] + 1, pre[3] + 1}) << " " <<
min({now[1] + 1, now[2] + 1, now[0], now[3]}) - min({pre[1] + 1, pre[2] + 1,pre[0], pre[3]}) << endl;
sumC[par[v]] += min({now[1], now[2], now[0] + 1, now[3] + 1}) - min({pre[1], pre[2],pre[0] + 1, pre[3] + 1});
sumD[par[v]] += min({now[1] + 1, now[2] + 1, now[0], now[3]}) - min({pre[1] + 1, pre[2] + 1,pre[0], pre[3]});
v = par[v];
}
}
int cat(int v) {
state[v] = 1;
query(v);
array<int,4> tmp = tree[1].get(1,1,cnt[1],1,cnt[1]);
int D = min({tmp[0], tmp[3], tmp[2] + 1, tmp[1] + 1});
int C = min({tmp[0] + 1, tmp[3] + 1, tmp[2], tmp[1]});
return min(D,C);
}
int dog(int v) {
state[v] = 2;
query(v);
array<int,4> tmp = tree[1].get(1,1,cnt[1],1,cnt[1]);
int D = min({tmp[0], tmp[3], tmp[2] + 1, tmp[1] + 1});
int C = min({tmp[0] + 1, tmp[3] + 1, tmp[2], tmp[1]});
return min(D,C);
}
int neighbor(int v) {
state[v] = 0;
query(v);
array<int,4> tmp = tree[1].get(1,1,cnt[1],1,cnt[1]);
int D = min({tmp[0], tmp[3], tmp[2] + 1, tmp[1] + 1});
int C = min({tmp[0] + 1, tmp[3] + 1, tmp[2], tmp[1]});
return min(D,C);
}
//void file(string name) {
// if (fopen((name + ".inp").c_str(), "r")) {
// freopen((name + ".inp").c_str(), "r", stdin);
// freopen((name + ".out").c_str(), "w", stdout);
// }
//}
//signed main() {
// file("DOGCAT");
// int n; cin >> n;
// vector<int> A,B;
// for (int i = 1; i < n; i++) {
// int x,y; cin >> x >> y;
// A.push_back(x);
// B.push_back(y);
// }
// initialize(n,A,B);
// int q; cin >> q;
// for (int i = 1; i <= q; i++) {
// int t,x; cin >> t >> x;
// if (t==1) cout << cat(x) << endl;
// else if (t==2) cout << dog(x) << endl;
// else cout << neighbor(x) << endl;
// }
//}