In this HackerEarth Fruits in a state problem solution, There are n states in a country. The states are connected to each other by undirected borders and there are total n - 1 borders between different pairs of states. These borders form a tree. The strength of a border i is ten[i].
Each state grows some fruits. Initially, there are no fruits in any state. The rate at which a fruit is grown in state i is R[i] per unit time. A country that is defined as a tree of connected states is considered rich at an instant if all the states contain at least X fruits.
A company wants to buy these fruits. It buys fruits from the state that contains the lowest production rate in the country and it visits a country only if it is rich. If there are multiple such countries, the company randomly chooses one state and buys from it.
You are required to answer q queries that are represented as follows:
The ith query consists of three space-separated integers ai, bi, ci. They allow you to generate Di, Ti, and Xi as Di = ai^ansi-1, Ti = bi ^ ansi-1, and Xi = ci^ansi-1, where ansi is the answer to the it query and ans0 = 0.
At t = 0, borders whose strength value is greater than Di splits apart and the remaining connected states form separate countries. Your task is to determine the total number of fruits that the company can collect at time Ti.
HackerEarth Fruits in a state problem solution.
#include <bits/stdc++.h>
typedef long double ld ;
#define long long long int
using namespace std;
#define mp make_pair
#define pb push_back
#define x first
#define y second
typedef pair<long,long> pll;
const int N=2e5+1;
const int R=1e5+1;
const int LOGR=20;
const int SEG_TREE=N*LOGR*3+4*R;
const int OTHER=1e8+1;
const long QUER_CONS=1L<<62;
vector<pair<int,long>> graph[N];
long rate[N];
int lef[SEG_TREE],rig[SEG_TREE];
long val[SEG_TREE];
int root[SEG_TREE];
vector<pair<long,pair<int,int>>> edges;
int rankk[N];
int parent[N];
int min_rate_country[N];
int max_rate_country[N];
int node_no=0;
int get_parent(int i)
{
if(i!=parent[i])
parent[i]=get_parent(parent[i]);
return parent[i];
}
void unite(int x,int y)
{
if(rankk[x]<rankk[y])
unite(y,x);
else
{
parent[y]=x;
min_rate_country[x]=min(min_rate_country[x],min_rate_country[y]);
max_rate_country[x]=min(max_rate_country[x],max_rate_country[y]);
if(rankk[x]==rankk[y])
rankk[x]++;
}
}
int check_connected(int node,int pa)
{
int temp=1;
for(auto itr:graph[node])
{
if(itr.x==pa)
continue;
temp+=check_connected(itr.x,node);
}
return temp;
}
int build(int s,int e)
{
int cur_node=++node_no;
val[cur_node]=0;
if(s!=e)
{
int mid=(s+e)/2;
lef[cur_node]=build(s,mid);
rig[cur_node]=build(mid+1,e);
}
else
{
lef[cur_node]=0;
rig[cur_node]=0;
}
return cur_node;
}
void update(int node,int s,int e,int pos,long change)
{
val[node]+=change;
if(s==e)
return;
int mid=(s+e)/2;
if(pos>mid)
update(rig[node],mid+1,e,pos,change);
else
update(lef[node],s,mid,pos,change);
}
int update_new(int node,int s,int e,int pos,long change)
{
int cur_node=++node_no;
val[cur_node]=val[node]+change;
if(s==e)
{
lef[cur_node]=0;
rig[cur_node]=0;
return cur_node;
}
int mid=(s+e)/2;
if(pos>mid)
{
lef[cur_node]=lef[node];
rig[cur_node]=update_new(rig[node],mid+1,e,pos,change);
}
else
{
rig[cur_node]=rig[node];
lef[cur_node]=update_new(lef[node],s,mid,pos,change);
}
return cur_node;
}
long query(int node,int s,int e,int pos)
{
// cout<<node<<" "<<s<<" "<<e<<" "<<pos<<endl;
if(s==e)
{
if(pos!=s)
return 0;
return val[node];
}
int mid=(s+e)/2;
if(pos>mid)
return query(rig[node],mid+1,e,pos);
else
return query(lef[node],s,mid,pos)+val[rig[node]];
}
int get_index(int n,long sep)
{
int ans=-1;
int lef=0,rig=n-2;
while(lef<=rig)
{
int mid=(lef+rig)/2;
if(edges[mid].x<sep)
{
ans=mid;
lef=mid+1;
}
else
rig=mid-1;
}
return ans;
}
void setup(int n)
{
sort(edges.begin(),edges.end());
for(int i=1;i<=n;i++)
{
rankk[i]=0;
parent[i]=i;
min_rate_country[i]=rate[i];
max_rate_country[i]=rate[i];
}
root[0]=build(0,N-1);
for(int i=1;i<=n;i++)
update(root[0],0,N-1,rate[i],rate[i]);
// cout<<"Built Seg Tree"<<endl;
for(int i=0;i<n-1;i++)
{
int u=edges[i].y.x;
int v=edges[i].y.y;
u=get_parent(u);
v=get_parent(v);
root[i+1]=update_new(root[i],0,N-1,min_rate_country[u],-max_rate_country[u]);
root[i+1]=update_new(root[i+1],0,N-1,min_rate_country[v],-max_rate_country[v]);
unite(u,v);
v=get_parent(v);
root[i+1]=update_new(root[i+1],0,N-1,min_rate_country[v],max_rate_country[v]);
}
}
long ans_query(long d,long t,long x,int n)
{
if(t==0)
return 0;
long min_rate=(x+t-1)/t;
int ind=get_index(n,d+1)+1;
return query(root[ind],0,N-1,min_rate)*t;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
srand(time(NULL));
// clock_t clk = clock();
int t=1;
while(t--)
{
int n,q;
cin>>n>>q;
assert(1<=n && n<N);
assert(1<=q && q<N);
for(int i=1;i<n;i++)
{
int u,v,w;
cin>>u>>v>>w;
assert(1<=u && u<=n);
assert(1<=v && v<=n);
assert(0<=w && w<OTHER);
graph[u].pb({v,w});
graph[v].pb({u,w});
edges.pb({w,{u,v}});
}
assert(check_connected(1,-1)==n);
for(int i=1;i<=n;i++)
{
cin>>rate[i];
assert(0<=rate[i] && rate[i]<R);
}
setup(n);
// cout<<"Built Persistence Seg Tree"<<endl;
long prev_ans=0;
for(int i=0;i<q;i++)
{
long d,t,x;
cin>>d>>t>>x;
// cout<<d<<" "<<t<<" "<<x<<" "<<prev_ans<<" Prev"<<endl;
assert(0<=d && d<QUER_CONS);
assert(0<=t && t<QUER_CONS);
assert(0<=x && x<QUER_CONS);
d=d^prev_ans;
t=t^prev_ans;
x=x^prev_ans;
// cout<<d<<" "<<t<<" "<<x<<" "<<prev_ans<<" Next"<<endl;
assert(0<=d && d<OTHER);
assert(0<=t && t<OTHER);
assert(0<=x && x<OTHER);
prev_ans=ans_query(d,t,x,n);
cout<<prev_ans<<"\n";
}
// clk = clock() - clk;
// cout << "Time Elapsed: " << fixed << setprecision(10) << ((double)clk)/CLOCKS_PER_SEC << "\n";
}
return 0;
}Second solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 14;
int n, q, ten[maxn], r[maxn], from[maxn], to[maxn];
struct Dsu{
int par[maxn];
Dsu(){ memset(par, -1, sizeof par); }
Dsu& operator = (const Dsu &od){
memcpy(par, od.par, sizeof par);
return *this;
}
int root(int v){
return par[v] == -1 ? v : par[v] = root(par[v]);
}
bool fri(int v, int u){
return root(v) == root(u);
}
bool merge(int v, int u){
return (v = root(v)) == (u = root(u)) ? 0 : (par[v] = u, 1);
}
};
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
for(int i = 0; i < n - 1; i++){
cin >> from[i] >> to[i] >> ten[i];
from[i]--, to[i]--;
}
for(int i = 0; i < n; i++)
cin >> r[i];
ll l = 0;
while(q--){
int d, t, x;
cin >> d >> t >> x;
d ^= l, t ^= l, x ^= l;
Dsu dsu;
for(int i = 0; i < n - 1; i++)
if(ten[i] <= d)
dsu.merge(from[i], to[i]);
ll mn[n], mx[n];
memset(mn, 63, sizeof mn);
memset(mx, -63, sizeof mn);
for(int i = 0; i < n; i++){
ll vi = (ll) t * r[i];
mn[dsu.root(i)] = min(mn[dsu.root(i)], vi);
mx[dsu.root(i)] = max(mx[dsu.root(i)], vi);
}
ll ans = 0;
for(int i = 0; i < n; i++)
if(dsu.par[i] == -1 && mn[i] >= x)
ans += mx[i];
cout << ans << '\n';
l = ans;
}
}
0 Comments