//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "catdog.h"
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;
struct tree {
struct node {
int dp[2][2];
};
vector<node> seg;
int sz;
void merge(int idx) {
seg[idx].dp[0] = {INF,INF};
seg[idx].dp[1] = {INF,INF};
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
for (int l = 0; l < 2; l++)
seg[idx].dp[i][l] = min(seg[idx].dp[i][l], seg[idx*2].dp[i][j] + (j ^ k) + seg[idx*2+1].dp[k][l]);
}
void upd(int idx, int l, int r) {
idx += sz;
seg[i].dp[0][0] += l;
seg[i].dp[1][1] += r;
for (idx /= 2; idx > 0; idx /= 2)
merge(idx);
}
void qry(int &l, int &r) {
l = min(min(seg[1].dp[0][0],seg[1].dp[0][1]), min(seg[1].dp[1][0],seg[1].dp[1][1])+1);
r = min(min(seg[1].dp[0][0],seg[1].dp[0][1])+1, min(seg[1].dp[1][0],seg[1].dp[1][1]));
}
void init(int n) {
sz = 1; while (sz < n) sz <<= 1;
seg.resize(sz * 2);
for (int i = s; i < 2*s; i++) {
seg[i].dp[0] = {0,0};
seg[i].dp[1] = {INF,INF};
}
for (int i = s-1; i > 0; i--)
merge(i);
}
} seg[MAXN];
vi adj[MAXN];
int sz[MAXN], par[MAXN], cnt = 0, len[MAXN], root[MAXN], pos[MAXN];
int n, cur[MAXN], col[MAXN];
void upd(int v, int l, int r) {
int a = 0, b = 0, c = 0, d = 0;
while (v != -1) {
int cur = col[v];
seg[cur].qry(a, b);
seg[cur].upd(pos[v], l, r);
seg[cur].qry(c, d);
l = c - a;
r = d - b;
v = root[cur];
}
seg[0].qry(a, b);
return min(a, b);
}
int getSz(int u, int p) {
sz[u] = 1;
par[u] = p;
for (int v: adj[u])
if (v != p)
sz[u] += sz[v];
return sz[u];
}
void dfs(int u, int p, int cur) {
col[u] = cur;
if (len[u] == 0)
root[cur] = p;
pos[u] = len[u]++;
pii nx = mp(0, -1);
for (int v: adj[u])
if (v != p)
nx = max(nx, mp(sz[v], v));
for (int v: adj[u]) {
if (v == p) continue;
if (v == nx.se)
dfs(v, u, cur);
else
dfs(v, u, cnt++);
}
}
void initialize(int N, vi A, vi B) {
n = N;
for (int i = 0; i+1 < N; i++) {
A[i]--, B[i]--;
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
dfs(0, -1);
dfs(0, -1, cnt++);
for (int i = 1; i <= cnt; i++)
seg[i].init(len[i]);
}
void dfs(int u, int p) {
if (cur[u] == 1)
dp[u][1] = INF;
else if (cur[u] == 2)
dp[u][0] = INF;
int a = 0, b = 0;
for (int v: adj[u]) {
if (v == p)
continue;
dfs(v, u);
if (cur[u] == 1)
dp[u][0] += min(dp[v][0], dp[v][1] + 1);
else if (cur[u] == 2)
dp[u][1] += min(dp[v][1], dp[v][0] + 1);
else {
a += min(dp[v][0], dp[v][1] + 1);
b += min(dp[v][1], dp[v][0] + 1);
}
}
if (cur[u] == 0)
dp[u][0] = a, dp[u][1] = b;
}
int cat(int v) {
v--;
int ret = upd(v, MAXN, 0);
cur[v] = 1;
return ret;
}
int dog(int v) {
v--;
int ret = upd(v, 0, MAXN);
cur[v] = 2;
return ret;
}
int neighbor(int v) {
v--;
int ret;
if (cur[v] == 1)
upd(v, -MAXN, 0);
else
upd(v, 0, -MAXN);
cur[v] = 0;
return ret;
}
Compilation message
catdog.cpp: In member function 'void tree::merge(int)':
catdog.cpp:41:28: error: assigning to an array from an initializer list
seg[idx].dp[0] = {INF,INF};
^
catdog.cpp:42:28: error: assigning to an array from an initializer list
seg[idx].dp[1] = {INF,INF};
^
catdog.cpp: In member function 'void tree::upd(int, int, int)':
catdog.cpp:52:7: error: 'i' was not declared in this scope
seg[i].dp[0][0] += l;
^
catdog.cpp:52:7: note: suggested alternative: 'pi'
seg[i].dp[0][0] += l;
^
pi
catdog.cpp: In member function 'void tree::init(int)':
catdog.cpp:66:16: error: 's' was not declared in this scope
for (int i = s; i < 2*s; i++) {
^
catdog.cpp:66:16: note: suggested alternative: 'sz'
for (int i = s; i < 2*s; i++) {
^
sz
catdog.cpp:67:23: error: assigning to an array from an initializer list
seg[i].dp[0] = {0,0};
^
catdog.cpp:68:27: error: assigning to an array from an initializer list
seg[i].dp[1] = {INF,INF};
^
catdog.cpp:70:16: error: 's' was not declared in this scope
for (int i = s-1; i > 0; i--)
^
catdog.cpp:70:16: note: suggested alternative: 'sz'
for (int i = s-1; i > 0; i--)
^
sz
catdog.cpp: In function 'void upd(int, int, int)':
catdog.cpp:91:17: error: return-statement with a value, in function returning 'void' [-fpermissive]
return min(a, b);
^
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:128:11: error: too few arguments to function 'void dfs(int, int, int)'
dfs(0, -1);
^
catdog.cpp:103:6: note: declared here
void dfs(int u, int p, int cur) {
^~~
catdog.cpp: In function 'void dfs(int, int)':
catdog.cpp:136:3: error: 'dp' was not declared in this scope
dp[u][1] = INF;
^~
catdog.cpp:136:3: note: suggested alternative: 'p'
dp[u][1] = INF;
^~
p
catdog.cpp:138:3: error: 'dp' was not declared in this scope
dp[u][0] = INF;
^~
catdog.cpp:138:3: note: suggested alternative: 'p'
dp[u][0] = INF;
^~
p
catdog.cpp:145:4: error: 'dp' was not declared in this scope
dp[u][0] += min(dp[v][0], dp[v][1] + 1);
^~
catdog.cpp:145:4: note: suggested alternative: 'p'
dp[u][0] += min(dp[v][0], dp[v][1] + 1);
^~
p
catdog.cpp:147:4: error: 'dp' was not declared in this scope
dp[u][1] += min(dp[v][1], dp[v][0] + 1);
^~
catdog.cpp:147:4: note: suggested alternative: 'p'
dp[u][1] += min(dp[v][1], dp[v][0] + 1);
^~
p
catdog.cpp:149:13: error: 'dp' was not declared in this scope
a += min(dp[v][0], dp[v][1] + 1);
^~
catdog.cpp:149:13: note: suggested alternative: 'p'
a += min(dp[v][0], dp[v][1] + 1);
^~
p
catdog.cpp:154:3: error: 'dp' was not declared in this scope
dp[u][0] = a, dp[u][1] = b;
^~
catdog.cpp:154:3: note: suggested alternative: 'p'
dp[u][0] = a, dp[u][1] = b;
^~
p
catdog.cpp: In function 'int cat(int)':
catdog.cpp:159:26: error: void value not ignored as it ought to be
int ret = upd(v, MAXN, 0);
^
catdog.cpp: In function 'int dog(int)':
catdog.cpp:166:26: error: void value not ignored as it ought to be
int ret = upd(v, 0, MAXN);
^
