#include "catdog.h"
#include <bits/stdc++.h>
#define MN 107171
#define INF int(1e7)
#pragma GCC optimize("unroll-loops")
using namespace std;
int x;
struct cost {int V[2][2]; } V[4 * MN];
namespace AINT {
int len;
cost nil;
cost uni(const cost &a, const cost &b) {
cost r;
for(int i = 0; i < 2; ++i)
for(int j = 0; j < 2; ++j)
r.V[i][j] = INF;
for(int i = 0; i < 2; ++i)
for(int j = 0; j < 2; ++j)
for(int k = 0; k < 2; ++k)
for(int f = 0; f < 2; ++f)
r.V[i][f] = min(r.V[i][f], a.V[i][j] + b.V[k][f] + (j != k));
return r;
}
void update(int p, cost v, int u = 1, int s = 1, int d = len) {
if(d < p || p < s) return;
if(s == d) {
V[u] = v;
return;
}
update(p, v, u * 2, s, (s + d) >> 1);
update(p, v, u * 2 + 1, (s + d) / 2 + 1, d);
V[u] = uni(V[u * 2], V[u * 2 + 1]);
V[u] = V[u];
}
cost query_i(int l, int r, int u = 1, int s = 1, int d = len) {
if(r < s || d < l) return nil;
if(l <= s && d <= r) return V[u];
return uni(query_i(l, r, u * 2, s, (s + d) / 2),
query_i(l, r, u * 2 + 1, (s + d) / 2 + 1, d));
}
}
/// 0 - cat 1 - dog
vector<int> L[MN];
int heavySon[MN], sz[MN], Par[MN], Nod[MN];
void dfs1(int u, int p) {
sz[u] = 1;
Par[u] = p;
int fiu_h = -1, s_fiu = -1;
for(auto it : L[u])
if(it != p) {
dfs1(it, u), sz[u] += sz[it];
if(sz[it] > s_fiu) {
s_fiu = sz[it];
fiu_h = it;
}
}
heavySon[u] = fiu_h;
}
int Dp0[MN], Dp1[MN]; // pt nodurile rascruce, dp-ul pt fiecare componenta
///Dp0 si Dp1 sunt influentele exterioare asupra unui element, nu costul real!
//asign id's
int StartComp[MN], EndComp[MN], NodePoz[MN], ParComp[MN], COUNTER_GLOBAL, COMP_GLOB, Comp[MN];
///la Start e pusa radacina lantului, la End ultimul nod!
void dfs2(int u, int p, int cul) {
NodePoz[u] = ++COUNTER_GLOBAL;
Nod[COUNTER_GLOBAL] = u;
if(!StartComp[cul]) StartComp[cul] = NodePoz[u];
EndComp[cul] = max(EndComp[cul], NodePoz[u]);
Comp[u] = cul;
if(sz[u] != 1)
dfs2(heavySon[u], u, cul);
for(auto it : L[u])
if(it != p && it != heavySon[u]) {
ParComp[++COMP_GLOB] = cul;
dfs2(it, u, COMP_GLOB);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
for(int i = 0; i < N - 1; ++i)
L[A[i]].push_back(B[i]), L[B[i]].push_back(A[i]);
dfs1(1, 0);
dfs2(1, 0, ++COMP_GLOB);
AINT::len = COUNTER_GLOBAL;
}
int Cul[MN];
int RealDP0[MN], RealDP1[MN];
cost calcnod(int u) {
cost nou;
for(int i = 0; i < 2; ++i)
for(int j = 0; j < 2; ++j)
nou.V[i][j] = INF;
for(int i = 0; i < 2; ++i)
for(int j = 0; j < 2; ++j){
nou.V[i][j] = min(nou.V[i][j], (Cul[u] == 1 ? INF : Dp0[u]) + i + j);
nou.V[i][j] = min(nou.V[i][j], (Cul[u] == 0 ? INF : Dp1[u]) + !i + !j);
}
return nou;
}
void update(int u, int val) {
Cul[u] = val;
AINT::update(NodePoz[u], calcnod(u));
int cur_comp = Comp[u];
while(cur_comp) {
//valoare parinte
cost val = AINT::query_i(StartComp[cur_comp], EndComp[cur_comp]);
u = Nod[StartComp[cur_comp]];
int last0 = RealDP0[u], last1 = RealDP1[u];
RealDP0[u] = min(val.V[0][0], val.V[0][1]);
RealDP1[u] = min(val.V[1][0], val.V[1][1]);
int delta0par = 0, delta1par = 0;
delta0par = min(RealDP1[u] + 1, RealDP0[u]) - min(last1 + 1, last0);
delta1par = min(RealDP0[u] + 1, RealDP1[u]) - min(last0 + 1, last1);
int parc = ParComp[cur_comp], par = Par[u];
Dp0[par] += delta0par;
Dp1[par] += delta1par;
AINT::update(NodePoz[par], calcnod(par));
cur_comp = parc;
u = par;
}
}
int cat(int v) {
update(v, 0);
return min(Dp0[0], Dp1[0]);
}
int dog(int v) {
update(v, 1);
return min(Dp0[0], Dp1[0]);
}
int neighbor(int v) {
update(v, -1);
return min(Dp0[0], Dp1[0]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2832 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2832 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2832 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
