In this HackerEarth Comrades - III problem The human army has proved itself against the mighty aliens by winning the Great War.
But even in times of peace, the army should remain alert and disciplint.
The army has N soldiers. The soldiers are numbered from 1 to N. The army has a superiority hierarchy. Every soldier has one immediate superior. The superior of a superior of a soldier is also a superior to that soldier. So, a soldier may have one or more superiors but only one immediate superior.
As a exercise to determine the efficiency of the army, the following drill has been designed.
You are given a list of orders. Each order is of the form "<Type><space><ID>"
where Type is either 1,2 or 3 and ID is a number S (1<=S<=N) that denotes a soldier.
There are three types of orders:
Type 1:
All the soldiers who have S as one of their superior will wake up.
Type 2:
All the soldiers who have S as one of their superior will go to sleep.
Type 3:
Count and output the number of soldiers who are awake and have S as one of their superior.
NOTE: Among all soldiers there is one soldier who does not have any superior. He is the commander of the whole army.
HackerEarth Comrades - III problem solution.
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 100000
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)>(y)?(x):(y))
vector<int> adj[MAX_N+1];
int startat[MAX_N+1],endat[MAX_N+1];
int status[MAX_N+1],status_size;
int tree[2*(MAX_N+1)],leftone[2*(MAX_N+1)],rightone[2*(MAX_N+1)];
int lazy[2*(MAX_N+1)];
int curmake;
int n;
void dfs(int at,int *done)
{
//cout<<"at "<<at<<endl;
if(done[at]==1)
return;
done[at]=1;
status[status_size]=1;
startat[at]=status_size;
#ifdef DEBUG
cout<<"startat of "<<at<<" is "<<startat[at]<<endl;
#endif
status_size++;
vector<int>::iterator it=adj[at].begin();
while(it!=adj[at].end())
{
dfs(*it,done);
it++;
}
endat[at]=status_size-1;
#ifdef DEBUG
cout<<"endat of "<<at<<" is "<<endat[at]<<endl;
#endif
}
void make(int thisone,int atl,int atr)
{
if(atl==atr)
{
tree[curmake]=1;
leftone[curmake]=-1;
rightone[curmake]=-1;
curmake++;
return;
}
int mid=(atl+atr)/2;
curmake++;
leftone[thisone]=curmake;
make(curmake,atl,mid);
if(mid+1<=atr)
{
rightone[thisone]=curmake;
make(curmake,mid+1,atr);
}
else
{
rightone[thisone]=-1;
}
tree[thisone]=atr-atl+1;
lazy[thisone]=0;
return;
}
void evallazy(int at,int atl,int atr)
{
if(lazy[at]!=0)
{
if(lazy[at]==1)
{
tree[at]=atr-atl+1;
}
else if(lazy[at]==-1)
{
tree[at]=0;
}
if(leftone[at]!=-1)
lazy[leftone[at]]=lazy[at];
if(rightone[at]!=-1)
lazy[rightone[at]]=lazy[at];
lazy[at]=0;
}
return;
}
void command(int at,int atl,int atr,int targetl,int targetr,int type)
{
evallazy(at,atl,atr);
if(atl==targetl && atr==targetr)
{
if(leftone[at]!=-1)
lazy[leftone[at]]=type;
if(rightone[at]!=-1)
lazy[rightone[at]]=type;
if(type==1)
tree[at]=atr-atl+1;
else
tree[at]=0;
return;
}
int mid=(atl+atr)/2;
if(mid>=targetl)
command(leftone[at],atl,mid,targetl,MIN(targetr,mid),type);
if(mid+1<=targetr)
command(rightone[at],mid+1,atr,MAX(mid+1,targetl),targetr,type);
evallazy(leftone[at],atl,mid);
evallazy(rightone[at],mid+1,atr);
tree[at]=tree[leftone[at]]+tree[rightone[at]];
return;
}
int check(int at,int atl,int atr,int targetl,int targetr)
{
#ifdef DEBUG
// cout<<" at "<<at<<" atl "<<atl<<" atr "<<atr<<" targetl "<<targetl<<" targetr "<<targetr<<endl;
// int ch;
// cin>>ch;
#endif
evallazy(at,atl,atr);
if(atl==targetl && atr==targetr)
{
return tree[at];
}
int mid=(atl+atr)/2;
int leftonew=0,rightonew=0;
if(mid>=targetl)
leftonew=check(leftone[at],atl,mid,targetl,MIN(targetr,mid));
if(mid+1<=targetr)
rightonew=check(rightone[at],mid+1,atr,MAX(mid+1,targetl),targetr);
evallazy(leftone[at],atl,mid);//needed or not?
evallazy(rightone[at],mid+1,atr);
tree[at]=tree[leftone[at]]+tree[rightone[at]];
return leftonew+rightonew;
}
void traverse(int at,int atl,int atr)
{
cout<<"at: "<<at<<" atl: "<<atl<<" atr: "<<atr<<" lazy: "<<lazy[at]<<" value: "<<tree[at]<<"left: "<<leftone[at]<<" right:"<<rightone[at]<<endl;
int mid=(atl+atr)/2;
if(atl!=atr)
{
traverse(leftone[at],atl,mid);
traverse(rightone[at],mid+1,atr);
}
}
int main()
{
int i,j,a,b,c,first;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>b;
if(b==0)
first=i;
else
{
adj[i].push_back(b);
adj[b].push_back(i);
}
}
status_size=0;
int done[MAX_N+1]={0};
dfs(first,done);
curmake=0;
make(0,0,status_size-1);
int q;
cin>>q;
while(q--)
{
int type,id;
cin>>type>>id;
switch(type)
{
case 1:
if(startat[id]!=endat[id])
command(0,0,status_size-1,startat[id]+1,endat[id],1);
break;
case 2:
if(startat[id]!=endat[id])
command(0,0,status_size-1,startat[id]+1,endat[id],-1);
break;
case 3:
int ans;
if(startat[id]!=endat[id])
ans=check(0,0,status_size-1,startat[id]+1,endat[id]);
else
ans=0;
cout<<ans<<endl;
break;
}
}
return 0;
}Second solution
#include<bits/stdc++.h>
using namespace std;
#define vi vector < int >
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define foreach(it,v) for( __typeof((v).begin())it = (v).begin() ; it != (v).end() ; it++ )
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 2000000000
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }
#define all(x) x.begin(),x.end()
#define mset(x, v) memset(x, v, sizeof(x))
#define si(x) (int)x.size()
#define N 100005
vi adj[N];
int tin[N],tout[N];
int timer;
void dfs(int cur,int par)
{
int i;
tin[cur] = ++timer;
for(i=0;i<adj[cur].size();i++)
{
int nxt = adj[cur][i];
if(nxt != par)
{
dfs(nxt,cur);
}
}
tout[cur] = timer;
}
struct node
{
int cnt;
int lazy;
}t[4*N];
void build(int node,int s,int e)
{
if(s == e)
{
t[node].cnt = 1;
t[node].lazy = 0;
return;
}
int m = (s+e)/2;
int c = 2*node;
build(c,s,m);
build(c+1,m+1,e);
t[node].cnt = t[c].cnt + t[c+1].cnt;
}
void update(int node,int s,int e,int x,int y,int v)
{
if(s > e)
return;
int m = (s+e)/2;
int c = 2*node;
if(t[node].lazy)
{
if(t[node].lazy == 1)
t[node].cnt = 0;
else
t[node].cnt = e - s + 1;
if(s != e)
{
t[c].lazy = t[c+1].lazy = t[node].lazy;
}
t[node].lazy = 0;
}
if(s > y || e < x)
return;
if(x <= s && e <= y)
{
if(v == 1)
t[node].cnt = 0;
else
t[node].cnt = e - s + 1;
if(s != e)
{
t[c].lazy = t[c+1].lazy = v;
}
return;
}
update(c,s,m,x,y,v);
update(c+1,m+1,e,x,y,v);
t[node].cnt = t[c].cnt + t[c+1].cnt;
}
int query(int node,int s,int e,int x,int y)
{
if(s > e || s > y || e < x)
return 0;
int m = (s+e)/2;
int c = 2*node;
if(t[node].lazy)
{
if(t[node].lazy == 1)
t[node].cnt = 0;
else
t[node].cnt = e - s + 1;
if(s != e)
{
t[c].lazy = t[c+1].lazy = t[node].lazy;
}
t[node].lazy = 0;
}
if(x <= s && e <= y)
{
return t[node].cnt;
}
return query(c,s,m,x,y) + query(c+1,m+1,e,x,y);
}
int main()
{
int n,i;
cin>>n;
assert(1 <= n && n <= 100000);
int root = -1;
for(i=1;i<=n;i++)
{
int j;
cin>>j;
assert(0 <= j && j <= n);
if(j == 0)
root = i;
else
adj[j].pb(i);
}
dfs(root,0);
build(1,1,n);
int q;
cin>>q;
assert(1 <= q && q <= 100000);
while(q--)
{
int op,u;
cin>>op>>u;
assert(1 <= op && op <= 3);
assert(1 <= u && u <= n);
if(op <= 2)
{
update(1,1,n,tin[u]+1,tout[u],3-op);
}
else
{
int ans = query(1,1,n,tin[u]+1,tout[u]);
cout<<ans<<endl;
}
}
return 0;
}
0 Comments