#include "catdog.h"
#include <bits/stdc++.h>
#define MN 100071
using namespace std;
///DEBUG
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char *s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template<typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for(const auto &x : v) {
if(!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
using state = pair<int, int>;
const int INF = 1e9;
const state CAT = {0, 1};
const state DOG = {1, 0};
const state EMPTY = {0, 0};
vector<int> L[MN];
int Sz[MN], HeavySon[MN], Nxt[MN];
int Par[MN], n;
int tmr, In[MN], Out[MN];
state Surplus[MN];
namespace AINT {
state V[4 * MN];
inline state uni(const state &a, const state &b) {
return make_pair(min({a.first + b.first, a.second + 1 + b.first, INF}), min({a.second + b.second, a.first + 1 + b.second, INF}));
}
void update(int p, state v, int u = 1, int s = 1, int d = tmr) {
if(d < p || p < s) return;
if(s == d) {
debug(u, s, d, p, v, Surplus[p], V[u]);
V[u] = v;
V[u].first += Surplus[p].first;
V[u].second += Surplus[p].second;
V[u].first = min(V[u].first, INF);
V[u].second = min(V[u].second, INF);
debug(V[u]);
return;
}
update(p, v, u << 1, s, (s + d) >> 1);
update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
V[u] = uni(V[u << 1], V[u << 1 | 1]);
debug(u, V[u]);
}
state query(int l, int r, int u = 1, int s = 1, int d = tmr) {
if(r < s || d < l) return {0, 0}; //nil
if(l <= s && d <= r) return V[u];
return uni(query(l, r, u << 1, s, (s + d) >> 1), query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d));
}
}
void dfs_sz(int u, int p, int pp) {
Sz[u] = 1;
for(auto &it : L[u])
if(it != p) {
dfs_sz(it, u, p), Sz[u] += Sz[it];
if(Sz[it] > Sz[L[u][0]] || L[u][0] == p) swap(it, L[u][0]);
}
}
void dfs_assign(int u, int p) {
In[u] = ++tmr;
Par[u] = p;
if(p) Nxt[u] = (L[p][0] == u ? Nxt[p] : u);
else Nxt[u] = u;
Out[Nxt[u]] = tmr;
for(auto it : L[u])
if(it != p) dfs_assign(it, u);
debug(u, In[u], Par[u], Nxt[u], Out[Nxt[u]], Sz[u]);
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for(int i = 0; i < int(A.size()); ++i)
L[A[i]].push_back(B[i]), L[B[i]].push_back(A[i]);
dfs_sz(1, 0, 0);
dfs_assign(1, 0);
}
void emul_prop(int u, stack<state> &UV) {
if(!u) return;
int head = Nxt[u];
int tail = Out[head];
int parinte_lant = Par[head];
emul_prop(parinte_lant, UV);
UV.push(AINT::query(In[head], tail));
}
state ValHut[MN];
void propag(int u, stack<state> &UltVal) { // va propaga in HLD update-ul facut asupra lui u
if(!u) return;
int head = Nxt[u];
int tail = Out[head];
state ls = UltVal.top(); UltVal.pop();
state now = AINT::query(In[head], tail);
state delta = {now.first - ls.first, now.second - ls.second};
int parinte_lant = Par[head];
debug(u, head, tail, parinte_lant, ls, now, delta, Surplus[parinte_lant]);
Surplus[parinte_lant].first += delta.first;
Surplus[parinte_lant].second += delta.second;
AINT::update(parinte_lant, ValHut[parinte_lant]); // il modific doar la surplus
propag(parinte_lant, UltVal);
}
int rez() {
state re = Surplus[0];
return min(re.first, re.second);
}
int cat(int v) {
debug("up0 pisi", v);
ValHut[v] = CAT;
stack<state> Old;
emul_prop(v, Old);
AINT::update(In[v], CAT);
propag(v, Old);
return rez();
}
int dog(int v) {
debug("up0 caine", v);
ValHut[v] = DOG;
stack<state> Old;
emul_prop(v, Old);
AINT::update(In[v], DOG);
propag(v, Old);
return rez();
}
int neighbor(int v) {
debug("up0 afara", v, ValHut[v]);
ValHut[v] = EMPTY;
stack<state> Old;
emul_prop(v, Old);
AINT::update(In[v], EMPTY);
propag(v, Old);
return rez();
}
Compilation message
catdog.cpp: In function 'void AINT::update(int, state, int, int, int)':
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
50 | #define debug(...) 42
| ^~
catdog.cpp:73:13: note: in expansion of macro 'debug'
73 | debug(u, s, d, p, v, Surplus[p], V[u]);
| ^~~~~
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
50 | #define debug(...) 42
| ^~
catdog.cpp:79:13: note: in expansion of macro 'debug'
79 | debug(V[u]);
| ^~~~~
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
50 | #define debug(...) 42
| ^~
catdog.cpp:85:9: note: in expansion of macro 'debug'
85 | debug(u, V[u]);
| ^~~~~
catdog.cpp: In function 'void dfs_assign(int, int)':
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
50 | #define debug(...) 42
| ^~
catdog.cpp:111:5: note: in expansion of macro 'debug'
111 | debug(u, In[u], Par[u], Nxt[u], Out[Nxt[u]], Sz[u]);
| ^~~~~
catdog.cpp: In function 'void propag(int, std::stack<std::pair<int, int> >&)':
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
50 | #define debug(...) 42
| ^~
catdog.cpp:141:5: note: in expansion of macro 'debug'
141 | debug(u, head, tail, parinte_lant, ls, now, delta, Surplus[parinte_lant]);
| ^~~~~
catdog.cpp: In function 'int cat(int)':
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
50 | #define debug(...) 42
| ^~
catdog.cpp:153:5: note: in expansion of macro 'debug'
153 | debug("up0 pisi", v);
| ^~~~~
catdog.cpp: In function 'int dog(int)':
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
50 | #define debug(...) 42
| ^~
catdog.cpp:163:5: note: in expansion of macro 'debug'
163 | debug("up0 caine", v);
| ^~~~~
catdog.cpp: In function 'int neighbor(int)':
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
50 | #define debug(...) 42
| ^~
catdog.cpp:173:5: note: in expansion of macro 'debug'
173 | debug("up0 afara", v, ValHut[v]);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
