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;
#define pb push_back
#define epb emplace_back
#define mp make_pair
#define all(a) begin(a), end(a)
#define csz(a) (int) a.size()
#define fori(i, a, b) for(int i = (int) a; i <= (int) b; ++i)
#define rofi(i, b, a) for(int i = (int) b; i >= (int) a; --i)
#define foreach(tt, a) for(auto &tt: a)
#define long long long
const int INF = 1e9+1;
const long MOD = 1e9+7, LINF = 1e16+1;
const int N = 1 << 17;
typedef array<array<int, 2>, 2> arr22;
int n, state[N];
pair<int,int> lastval[N];
vector<int> g[N];
int par[N], sz[N], in[N], nxt[N], down[N];
void dfs_sz(int u) {
sz[u] = 1;
foreach(v, g[u]) if(v != par[u]) {
par[v] = u;
dfs_sz(v);
sz[u] += sz[v];
if(g[u][0] == par[u] || sz[v] > sz[g[u][0]]) swap(v, g[u][0]);
}
}
void dfs_hld(int u) {
static int tick = 0;
in[u] = tick++;
down[nxt[u]] = u;
foreach(v, g[u]) if(v != par[u]) {
nxt[v] = (v == g[u][0] ? nxt[u] : v);
dfs_hld(v);
}
}
arr22 t[2*N];
arr22 merge(arr22 a, arr22 b) {
arr22 ret;
ret[0][0] = ret[0][1] = ret[1][0] = ret[1][1] = INF;
fori(i, 0, 1) fori(j, 0, 1) fori(x, 0, 1) fori(y, 0, 1) {
ret[i][j] = min(a[i][x] + b[y][j] + (x != y), ret[i][j]);
}
return ret;
}
void build(int i = 1, int l = 0, int r = N-1) {
if(l == r) {
t[i][0][1] = t[i][1][0] = INF;
return;
}
int mid = l+r >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid+1, r);
t[i] = merge(t[i << 1], t[i << 1 | 1]);
}
void update(int targ, pair<int,int> val, int i = 1, int l = 0, int r = N-1) {
if(l == r) {
t[i][0][0] += val.first, t[i][1][1] += val.second;
return;
}
int mid = l+r >> 1;
if(targ <= mid) update(targ, val, i << 1, l, mid);
else update(targ, val, i << 1 | 1, mid+1, r);
t[i] = merge(t[i << 1], t[i << 1 | 1]);
}
arr22 query(int tl, int tr, int i = 1, int l = 0, int r = N-1) {
if(l > tr || r < tl) {
arr22 ret;
fori(x, 0, 1) fori(y, 0, 1) ret[x][y] = 0;
return ret;
}
if(tl <= l && r <= tr) return t[i];
int mid = l+r >> 1;
arr22 lf = query(tl, tr, i << 1 , l, mid);
arr22 rg = query(tl, tr, i << 1 | 1, mid+1, r);
arr22 ret;
if(tr <= mid) ret = lf;
else if(tl > mid) ret = rg;
else ret = merge(lf, rg);
return ret;
}
void initialize(int _n, vector<int> U, vector<int> V) {
n = _n;
fori(i, 0, n-2) {
g[U[i]].pb(V[i]);
g[V[i]].pb(U[i]);
}
dfs_sz(1);
nxt[1] = 1;
dfs_hld(1);
build();
}
void propogate(int v, pair<int,int> val) {
while(v) {
update(in[v], val);
arr22 curr = query(in[nxt[v]], in[down[nxt[v]]]);
pair<int,int> mn = {min(curr[0][0], curr[0][1]), min(curr[1][0], curr[1][1])};
pair<int,int> mn2 = {min(mn.first, mn.second + 1), min(mn.first + 1, mn.second)};
val = mp(mn2.first - lastval[nxt[v]].first, mn2.second - lastval[nxt[v]].second);
lastval[nxt[v]] = mn2;
v = par[nxt[v]];
}
}
int answer() {
int ans = INF;
arr22 ret = query(in[1], in[down[1]]);
fori(i, 0, 1) fori(j, 0, 1) ans = min(ret[i][j], ans);
return ans;
}
int cat(int v) {
state[v] = 1;
propogate(v, mp(0, INF));
return answer();
}
int dog(int v) {
state[v] = 2;
propogate(v, mp(INF, 0));
return answer();
}
int neighbor(int v) {
if(state[v] == 1) propogate(v, mp(0, -INF));
else propogate(v, mp(-INF, 0));
return answer();
}
Compilation message (stderr)
catdog.cpp: In function 'void build(int, int, int)':
catdog.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l+r >> 1;
~^~
catdog.cpp: In function 'void update(int, std::pair<int, int>, int, int, int)':
catdog.cpp:67:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l+r >> 1;
~^~
catdog.cpp: In function 'arr22 query(int, int, int, int, int)':
catdog.cpp:79:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l+r >> 1;
~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |