#include <bits/stdc++.h>
#include "catdog.h"
#define DIM 100010
#define INF 1000000000
using namespace std;
vector <int> L[DIM],a,b;
int v[DIM];
int n,i,q,tip,x,nr_chains;
vector <int> chains[DIM];
int whatChain[DIM],positionInChain[DIM],chainFatherNode[DIM],s[DIM];
struct segment_tree{
long long dp[2][2];
};
vector <segment_tree> aint[DIM];
void dfs (int nod, int tata){
s[nod] = 1;
int ok = 0, maxi = 0, heavy_son = 0;
for (auto vecin : L[nod])
if (vecin != tata){
ok = 1;
dfs (vecin,nod);
s[nod] += s[vecin];
if (s[vecin] > maxi)
maxi = s[vecin], heavy_son = vecin;
}
if (!ok){
nr_chains++;
chains[nr_chains].push_back(0);
chains[nr_chains].push_back(nod);
positionInChain[nod] = 1;
whatChain[nod] = nr_chains;
} else {
chains[whatChain[heavy_son]].push_back(nod);
whatChain[nod] = whatChain[heavy_son];
positionInChain[nod] = chains[whatChain[heavy_son]].size()-1;
for (auto vecin : L[nod]){
if (vecin != tata && vecin != heavy_son)
chainFatherNode[whatChain[vecin]] = nod;
}
}
}
void update_nod (int chain, int nod){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
for (int i=0;i<=1;i++)
for (int j=0;j<=1;j++){
long long mini = 1LL * INF * INF;
for (int i2=0;i2<=1;i2++)
for (int j2=0;j2<=1;j2++)
mini = min (mini,aint[chain][fiu_st].dp[i][i2] + aint[chain][fiu_dr].dp[j2][j] + (i2 != j2));
aint[chain][nod].dp[i][j] = mini;
}
}
void build (int chain, int nod, int st, int dr){
if (st == dr){
aint[chain][nod].dp[0][0] = aint[chain][nod].dp[1][1] = 0;
aint[chain][nod].dp[0][1] = aint[chain][nod].dp[1][0] = INF;
return;
}
int mid = (st+dr)>>1;
build (chain,nod<<1,st,mid);
build (chain,(nod<<1)|1,mid+1,dr);
update_nod (chain,nod);
}
void update_aint (int chain, int nod, int st, int dr, int poz, long long val, long long val2){
if (st == dr){
aint[chain][nod].dp[0][0] += val;
aint[chain][nod].dp[1][1] += val2;
aint[chain][nod].dp[0][1] = aint[chain][nod].dp[1][0] = INF;
return;
}
int mid = (st+dr)>>1;
if (poz <= mid)
update_aint(chain,nod<<1,st,mid,poz,val,val2);
else update_aint(chain,(nod<<1)|1,mid+1,dr,poz,val,val2);
update_nod(chain,nod);
}
int query (){
long long mini = 1LL * INF * INF;
for (int i=0;i<=1;i++)
for (int j=0;j<=1;j++)
mini = min (mini,aint[ whatChain[1] ][1].dp[i][j]);
return mini;
}
void initialize(int _n, vector<int> A, vector<int> B) {
n = _n;
for (int i=0;i<n-1;i++){
L[A[i]].push_back(B[i]);
L[B[i]].push_back(A[i]);
}
dfs (1,0);
for (int i=1;i<=nr_chains;i++){
aint[i].resize(chains[i].size()*4);
//for (int j=0;j<=chains[i].size()*4;j++)
// aint[i].push_back();
build (i,1,1,chains[i].size()-1);
}
}
void update (int x, long long val, long long val2){
int chain = whatChain[x];
long long old_val0 = min (aint[chain][1].dp[0][0],aint[chain][1].dp[1][0]);
long long old_val1 = min (aint[chain][1].dp[0][1],aint[chain][1].dp[1][1]);
update_aint(chain,1,1,chains[chain].size()-1,positionInChain[x],val,val2);
long long new_val0 = min (aint[chain][1].dp[0][0],aint[chain][1].dp[1][0]);
long long new_val1 = min (aint[chain][1].dp[0][1],aint[chain][1].dp[1][1]);
int new_x = chainFatherNode[chain];
if (new_x)
update (new_x, min(new_val0,new_val1+1) - min(old_val0,old_val1+1), min(new_val1,new_val0+1) - min(old_val1,old_val1+0));
}
int cat(int x) {
v[x] = 1;
update (x,0,INF);
return query();
}
int dog(int x) {
v[x] = 2;
update (x,INF,0);
return query();
}
int neighbor(int x) {
if (v[x] == 1)
update (x,0,-INF);
if (v[x] == 2)
update (x,-INF,0);
v[x] = 0;
return query();
}
/*
int main (){
ifstream cin ("date.in");
ofstream cout ("date.out");
cin>>n;
for (i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
a.push_back(x);
b.push_back(y);
//cin>>a[i]>>b[i];
}
initialize(n,a,b);
cin>>q;
for (;q--;){
cin>>tip>>x;
if (tip == 1)
cout<<cat(x)<<"\n";
else {
if (tip == 2)
cout<<dog(x)<<"\n";
else cout<<neighbor(x)<<"\n";
}
}
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
7372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
7372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
7372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
