//#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 {
ll dp[2][2];
};
vector<node> seg;
int sz;
void merge(int idx) {
seg[idx].dp[0][0] = seg[idx].dp[0][1] = INF;
seg[idx].dp[1][0] = seg[idx].dp[1][1] = 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[idx].dp[0][0] += l;
seg[idx].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 = sz; i < 2*sz; i++) {
seg[i].dp[0][0] = seg[i].dp[1][1] = 0;
seg[i].dp[1][0] = seg[i].dp[0][1] = INF;
}
for (int i = sz-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];
int 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] += getSz(v, u);
return sz[u];
}
void dfs(int u, int p, int cur) {
col[u] = cur;
if (len[cur] == 0)
root[cur] = p;
pos[u] = len[cur]++;
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]);
}
getSz(0, -1);
dfs(0, -1, cnt++);
for (int i = 0; i < cnt; i++)
seg[i].init(len[i]);
}
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 function 'int neighbor(int)':
catdog.cpp:156:9: warning: 'ret' is used uninitialized in this function [-Wuninitialized]
return ret;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
