| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 96031 | onjo0127 | Cats or Dogs (JOI18_catdog) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
long long cc, cd, dc, dd;
};
struct segtree {
vector<node> tree;
segtree(int N) {
tree = vector<node>(4*N, {0, 1e9, 1e9, 0});
}
void pull(int idx) {
node l = tree[idx*2], r = tree[idx*2+1];
tree[idx].cc = min({l.cc + r.cc, l.cc + 1 + r.dc, l.cd + 1 + r.cc, l.cd + r.dc});
tree[idx].cd = min({l.cc + r.cd, l.cc + 1 + r.dd, l.cd + 1 + r.cd, l.cd + r.dd});
tree[idx].dc = min({l.dc + r.cc, l.dc + 1 + r.dc, l.dd + 1 + r.cc, l.dd + r.dc});
tree[idx].dd = min({l.dc + r.cd, l.dc + 1 + r.dd, l.dd + 1 + r.cd, l.dd + r.dd});
}
void upd(int idx, int s, int e, int p, int cat, int dog) {
if(p < s || e < p) return;
if(s == e) {
tree[idx] = {cat, 1e9, 1e9, dog};
return;
}
int m = s+e >> 1;
upd(idx*2, s, m, p, cat, dog);
upd(idx*2+1, m+1, e, p, cat, dog);
pull(idx);
}
};
int A[100009];
long long C[100009], D[100009];
vector<int> adj[100009];
vector<segtree> seg;
vector<vector<int> > paths;
int sz[100009], pid[100009], vid[100009];
int dfs(int x, int p) {
int s = 1;
for(auto& it: adj[x]) if(it != p) s += dfs(it, x);
return sz[x] = s;
}
void makeHLD(int x, int p) {
if(2*sz[x] >= sz[p] && x != 1) {
pid[x] = pid[p];
vid[x] = vid[p] + 1;
paths[pid[x]].push_back(x);
}
else {
pid[x] = paths.size();
vid[x] = 1;
paths.push_back({p, x});
}
for(auto& it: adj[x]) if(it != p) makeHLD(it, x);
}
void updHLD(int u, int cat, int dog) {
int pd = pid[u], vd = vid[u], rtp = paths[pd][0], rt = paths[pd][1];
node& srt = seg[pd].tree[1];
int crt = min(srt.cc, srt.cd), drt = min(srt.dc, srt.dd);
C[rtp] -= min(crt, drt + 1);
D[rtp] -= min(crt + 1, drt);
seg[pd].upd(1, 1, (int)paths[pd].size() - 1, vd, cat, dog);
crt = min(srt.cc, srt.cd); drt = min(srt.dc, srt.dd);
C[rtp] += min(crt, drt + 1);
D[rtp] += min(crt + 1, drt);
if(rtp != 0) updHLD(rtp, (A[rtp] == 2 ? 1e9: C[rtp]), (A[rtp] == 1 ? 1e9 : D[rtp]));
}
void initialize(int N, vector<int> A, vector<int> B) {
for(int i=0; i<N-1; i++) {
int u = A[i], v = B[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 1);
makeHLD(1, 0);
for(auto& it: paths) seg.push_back(segtree(it.size() - 1));
}
int ans() {
node& srt = seg[0].tree[1];
int crt = min(srt.cc, srt.cd), drt = min(srt.dc, srt.dd);
return min((A[1] == 2 ? 1e9: crt), (A[1] == 1 ? 1e9 : drt));
}
int cat(int v) {
A[v] = 1;
updHLD(v, C[v], 1e9);
return ans();
}
int dog(int v) {
A[v] = 2;
updHLD(v, 1e9, D[v]);
return ans();
}
int neighbor(int v) {
A[v] = 0;
updHLD(v, C[v], D[v]);
return ans();
}