#include "catdog.h"
#include <bits/stdc++.h>
#include <cstdio>
#include <cassert>
#include <vector>
#include <stdlib.h>
#define INF 1000005
using namespace std;
int x,tata[200005],niv[200005],nr,valoare[200005],mar[200005],max_fiu[200005];
vector <int> gr[200005];
void dfs(int x,int t,int nivel)
{
tata[x]=t;
niv[x]=nivel;
mar[x]=1;
for (int i=0; i<gr[x].size(); i++)
{
int nod=gr[x][i];
if (nod!=t)
{
dfs(nod,x,nivel+1);
mar[x]+=mar[nod];
if (mar[nod]>mar[max_fiu[x]])
{
max_fiu[x]=nod;
}
}
}
}
class SegmentTree
{
struct Nod
{
long long cost[2][2];
};
Nod *arb;
public:
void inline Initeaza(int nr)
{
arb = new Nod [((nr<<4)+1)];
for (int i=1;i<=(nr<<2);i++)
{
arb[i].cost[0][0]=arb[i].cost[1][1]=0;
arb[i].cost[1][0]=arb[i].cost[0][1]=INF;
}
for (int i=nr;i>=1;i--)
{
update(1,nr,1,i,arb[i]);
}
}
void inline update(int st,int dr,int nod,int poz, Nod val)
{
int a,b,c,d;
if (st==dr)
{
arb[nod]=val;
return;
}
int mij=(st+dr)/2;
if (poz<=mij)
{
update(st,mij,2*nod,poz,val);
}
else
{
update(mij+1,dr,2*nod+1,poz,val);
}
for (a=0;a<=1;a++)
{
for (b=0;b<=1;b++)
{
arb[nod].cost[a][b]=INF;
}
}
for (a=0;a<=1;a++)
{
for (b=0;b<=1;b++)
{
for (c=0;c<=1;c++)
{
for (d=0;d<=1;d++)
{
arb[nod].cost[a][d]=min(arb[nod].cost[a][d],arb[2*nod].cost[a][b]+arb[2*nod+1].cost[c][d]+(b^c));
}
}
}
}
}
void add(int st,int dr,int nod,int poz,int val1,int val2)
{
int a,b,c,d;
if (st==dr)
{
arb[nod].cost[0][0]+=val1;
arb[nod].cost[1][1]+=val2;
return;
}
int mij=(st+dr)/2;
if (poz<=mij)
{
add(st,mij,2*nod,poz,val1,val2);
}
else
{
add(mij+1,dr,2*nod+1,poz,val1,val2);
}
for (a=0;a<=1;a++)
{
for (b=0;b<=1;b++)
{
arb[nod].cost[a][b]=INF;
}
}
for (a=0;a<=1;a++)
{
for (b=0;b<=1;b++)
{
for (c=0;c<=1;c++)
{
for (d=0;d<=1;d++)
{
arb[nod].cost[a][d]=min(arb[nod].cost[a][d],arb[2*nod].cost[a][b]+arb[2*nod+1].cost[c][d]+(b^c));
}
}
}
}
}
pair <int,int> get()
{
int a,b,v0,v1;
a=min(arb[1].cost[0][0],arb[1].cost[0][1]);
b=min(arb[1].cost[1][0],arb[1].cost[1][1]);
v0=min(a,b+1);
v1=min(b,a+1);
return {v0,v1};
}
}*chains;
int id[200005],cnt[200005],q,primul[200005],poz[200005];
void split (int x,int t)
{
id[x]=q;
cnt[q]++;
poz[x]=cnt[q];
if (primul[q]==0)
{
primul[q]=x;
}
if (max_fiu[x]==0)
{
return;
}
split(max_fiu[x],x);
for (int i=0;i<gr[x].size();i++)
{
int nod=gr[x][i];
if (nod!=t&&nod!=max_fiu[x])
{
q++;
split(nod,x);
}
}
}
int n2;
void initialize(int n, std::vector<int> A, std::vector<int> B)
{
n2=n;
int i;
for (i=0; i<n-1; i++)
{
gr[A[i]].push_back(B[i]);
gr[B[i]].push_back(A[i]);
}
nr=0;
dfs(1,0,1);
q=1;
split(1,0);
chains = new SegmentTree [(q+1)];
for (i=1;i<=q;i++)
{
chains[i].Initeaza(cnt[i]);
}
}
pair <int,int> salut;
void update(int x,int v0,int v1)
{
while (x)
{
pair <int,int> inainte,acum;
inainte=chains[id[x]].get();
chains[id[x]].add(1,cnt[id[x]],1,poz[x],v0,v1);
acum=chains[id[x]].get();
v0=acum.first-inainte.first;
v1=acum.second-inainte.second;
x=tata[primul[id[x]]];
}
}
int cat(int v)
{
valoare[v]=1;
update(v,0,INF);
salut=chains[1].get();
return min(salut.first,salut.second);
}
int dog(int v)
{
valoare[v]=2;
update(v,INF,0);
salut=chains[1].get();
return min(salut.first,salut.second);
}
int neighbor(int v)
{
if (valoare[v]==1)
{
update(v,0,-INF);
salut=chains[1].get();
valoare[v]=0;
return min(salut.first,salut.second);
}
else
if (valoare[v]==2)
{
update(v,-INF,0);
salut=chains[1].get();
valoare[v]=0;
return min(salut.first,salut.second);
}
return 0;
}
/*int readInt(){
int i;
if(scanf("%d",&i)!=1){
fprintf(stderr,"Error while reading input\n");
exit(1);
}
return i;
}
int main(){
int N=readInt();
std::vector<int> A(N-1),B(N-1);
for(int i=0;i<N-1;i++)
{
A[i]=readInt();
B[i]=readInt();
}
int Q;
assert(scanf("%d",&Q)==1);
std::vector <int> T(Q),V(Q);
for(int i=0;i<Q;i++)
{
T[i]=readInt();
V[i]=readInt();
}
initialize(N,A,B);
std::vector<int> res(Q);
for(int j=0;j<Q;j++)
{
if(T[j]==1) res[j]=cat(V[j]);
else if(T[j]==2) res[j]=dog(V[j]);
else res[j]=neighbor(V[j]);
}
for(int j=0;j<Q;j++)
printf("%d\n",res[j]);
return 0;
}*/
Compilation message
catdog.cpp: In function 'void dfs(int, int, int)':
catdog.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i=0; i<gr[x].size(); i++)
| ~^~~~~~~~~~~~~
catdog.cpp: In function 'void split(int, int)':
catdog.cpp:154:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for (int i=0;i<gr[x].size();i++)
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
