In this HackerEarth Skrtel ! problem solution Stevie : "The more you play with Christmas Trees, the more addicted you are to them. Let's go on". Legends serve a club selflessly for ages without any noise off the pitch. Do you remember the headed goal vs the Gunners with a highly bandaged head by this guy : ?
You are given a Tree T consisting of N nodes where node i of the tree has number A[i] written on it. Now, you need to process 2 kinds of queries on this tree.
- X Y : Update the number written on node with index X to Y
- U V K : Find if the product of number written on each nodes lying on the path from node U to V is divisible by the number K.
The answer to the second kind of query is either a YES or NO .
HackerEarth Skrtel ! problem solution.
import java.io.*;
import java.util.*;
import java.math.*;
public final class solution
{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static FastScanner sc=new FastScanner(br);
static PrintWriter out=new PrintWriter(System.out);
static Random rnd=new Random();
static int[][] al;
static int[] x,y,a,tin,tout,sp,cnt;
static int[][] st;
static int maxn=(int)(2e5+5);
static int time=0;
static int LN=21;
static Map<Integer,Integer> m1;
static ArrayList<Node>[] events;
static Map<Integer,Integer>[] mp;
static int[] bit;
static void put(int idx,int val)
{
m1.put(idx,m1.getOrDefault(idx,0)+val);
}
static void build()
{
sp=new int[maxn];
for(int i=2;i<maxn;i++)
{
if(sp[i]==0)
{
for(int j=i;j<maxn;j+=i)
{
sp[j]=i;
}
}
}
}
static void dfs(int u,int p)
{
tin[u]=++time;st[0][u]=p;
for(int x:al[u])
{
if(x!=p)
{
dfs(x,u);
}
}
tout[u]=time;
}
static void update(int idx,int val)
{
while(idx<maxn)
{
bit[idx]+=val;idx+=idx&-idx;
}
}
static int query(int idx)
{
int ret=0;
while(idx>0)
{
ret=ret+bit[idx];idx-=idx&-idx;
}
return ret;
}
static void clear(int idx)
{
while(idx<maxn)
{
bit[idx]=0;idx+=idx&-idx;
}
}
static void solve(int num)
{
for(Node x:events[num])
{
if(x.a==1)
{
update(x.b,x.d);update(x.c,-x.d);
}
else
{
int curr=query(x.c)+query(x.d)-query(x.e)-(x.f==-1?0:query(x.f));
mp[x.b].put(num,mp[x.b].get(num)-curr);
}
}
for(Node x:events[num])
{
if(x.a==1)
{
clear(x.b);clear(x.c);
}
}
}
static boolean isAncestor(int u,int v)
{
return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}
static int lca(int u,int v)
{
if(isAncestor(u,v)) return u;
if(isAncestor(v,u)) return v;
for(int i=LN-1;i>=0;i--)
{
if(!isAncestor(st[i][u],v))
{
u=st[i][u];
}
}
return st[0][u];
}
@SuppressWarnings("unchecked")
public static void run() throws Exception
{
build();int n=sc.nextInt(),q=sc.nextInt();a=new int[n];cnt=new int[n];
if(n<1 || n>100000 || q<1 || q>100000) throw new Exception("Wrong");
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
if(a[i]<=1 && a[i]>200000) throw new Exception("Wrong");
}
x=new int[n];y=new int[n];
for(int i=1;i<n;i++)
{
x[i]=sc.nextInt()-1;y[i]=sc.nextInt()-1;
cnt[x[i]]++;cnt[y[i]]++;
if(x[i]>=y[i]) throw new Exception("Wrong");
}
al=new int[n][];bit=new int[maxn];
for(int i=0;i<n;i++)
{
al[i]=new int[cnt[i]];cnt[i]=0;
}
for(int i=1;i<n;i++)
{
al[x[i]][cnt[x[i]]++]=y[i];
al[y[i]][cnt[y[i]]++]=x[i];
}
tin=new int[n];tout=new int[n];st=new int[LN][n];dfs(0,0);
for(int i=1;i<LN;i++)
{
for(int j=0;j<n;j++)
{
st[i][j]=st[i-1][st[i-1][j]];
}
}
events=new ArrayList[maxn];
for(int i=1;i<maxn;i++)
{
events[i]=new ArrayList<Node>();
}
for(int i=0;i<n;i++)
{
m1=new HashMap<>();int curr=a[i];
while(curr>1)
{
put(sp[curr],1);curr/=sp[curr];
}
for(Map.Entry<Integer,Integer> en:m1.entrySet())
{
int key=en.getKey();
events[key].add(new Node(1,tin[i],tout[i]+1,en.getValue(),-1,-1));
}
}
mp=new HashMap[q];
for(int i=0;i<q;i++)
{
mp[i]=new HashMap<Integer,Integer>();
}
for(int i=0;i<q;i++)
{
int t=sc.nextInt();
if(t==1)
{
int x=sc.nextInt()-1;m1=new HashMap<>();
if(x<0 || x>=n) throw new Exception("Wrong");
int curr=a[x];
while(curr>1)
{
put(sp[curr],1);curr/=sp[curr];
}
for(Map.Entry<Integer,Integer> en:m1.entrySet())
{
int key=en.getKey();
events[key].add(new Node(1,tin[x],tout[x]+1,-en.getValue(),-1,-1));
}
a[x]=sc.nextInt();curr=a[x];m1=new HashMap<>();
if(curr<=1 && curr>200000) throw new Exception("Wrong");
while(curr>1)
{
put(sp[curr],1);curr/=sp[curr];
}
for(Map.Entry<Integer,Integer> en:m1.entrySet())
{
int key=en.getKey();
events[key].add(new Node(1,tin[x],tout[x]+1,en.getValue(),-1,-1));
}
}
else
{
int u=sc.nextInt()-1,v=sc.nextInt()-1,k=sc.nextInt(),lca=lca(u,v);
if(u<0 || u>=n || v<0 || v>=n || k<=1 || k>200000) throw new Exception("Wrong");
int curr=k;m1=new HashMap<>();
while(curr>1)
{
put(sp[curr],1);curr/=sp[curr];
}
for(Map.Entry<Integer,Integer> en:m1.entrySet())
{
int key=en.getKey();
events[key].add(new Node(2,i,tin[u],tin[v],tin[lca],lca==0?-1:tin[st[0][lca]]));
}
mp[i]=new HashMap<>(m1);
}
}
for(int i=2;i<maxn;i++)
{
solve(i);
}
for(int i=0;i<q;i++)
{
if(mp[i].size()!=0)
{
boolean ans=true;
for(Map.Entry<Integer,Integer> en:mp[i].entrySet())
{
if(en.getValue()>0)
{
ans=false;break;
}
}
out.println(ans?"YES":"NO");
}
}
out.close();
}
public static void main(String[] args) throws Exception
{
new Thread(null,new Runnable(){
public void run()
{
try
{
new solution().run();
}
catch(Exception e)
{
}
}
},"1",1<<28).start();
}
}
class Node
{
int a,b,c,d,e,f;
public Node(int a,int b,int c,int d,int e,int f)
{
this.a=a;this.b=b;this.c=c;this.d=d;this.e=e;this.f=f;
}
}
class FastScanner
{
BufferedReader in;
StringTokenizer st;
public FastScanner(BufferedReader in) {
this.in = in;
}
public String nextToken() throws Exception {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return st.nextToken();
}
public String next() throws Exception {
return nextToken().toString();
}
public int nextInt() throws Exception {
return Integer.parseInt(nextToken());
}
public long nextLong() throws Exception {
return Long.parseLong(nextToken());
}
public double nextDouble() throws Exception {
return Double.parseDouble(nextToken());
}
}
Second solution
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> pii;
const int LGN = 18;
const int MAXN = 200005;
struct event
{
int type, v1, v2, val, index;
event(int a, int b, int c)
{
type = 1;
v1 = b;
v2 = -1;
val = c;
index = a;
}
event(int a, int b, int c, int d)
{
type = 2;
v1 = b;
v2 = c;
val = d;
index = a;
}
};
bool sieve[MAXN], ans[MAXN];
int curr_time, factor[MAXN], cval[MAXN], depth[MAXN], BIT[MAXN], subtree_start[MAXN], subtree_end[MAXN], par[MAXN][LGN];
vector <int> G[MAXN];
vector <event> to_process[MAXN];
vector <pii> factorise(int x)
{
vector <pii> ret;
while(x > 1)
{
int ctr = 0, cfact = factor[x];
while(factor[x] == cfact)
{
ctr++;
x/=cfact;
}
ret.push_back(pii(cfact,ctr));
}
return ret;
}
void BIT_upd(int pos, int val)
{
while(pos < MAXN)
{
BIT[pos]+=val;
pos+=(pos & (-pos));
}
}
int BIT_get(int pos)
{
int ret = 0;
while(pos > 0)
{
ret+=BIT[pos];
pos-=(pos & (-pos));
}
return ret;
}
void add_val_to_subtree(int root, int val)
{
BIT_upd(subtree_start[root], val);
BIT_upd(subtree_end[root]+1, -val);
}
int get_path_val(int pos)
{
return BIT_get(subtree_start[pos]);
}
void dfs(int pos, int prev)
{
par[pos][0] = prev;
depth[pos] = depth[prev] + 1;
curr_time++;
subtree_start[pos] = curr_time;
for (int i = 0; i < G[pos].size(); ++i)
{
if(G[pos][i] != prev)
dfs(G[pos][i],pos);
}
subtree_end[pos] = curr_time;
}
int lca(int u, int v)
{
if(depth[u] < depth[v])
swap(u,v);
int diff = depth[u] - depth[v];
for (int i = 0; i < LGN; ++i)
{
if(diff & (1<<i))
u = par[u][i];
}
if(u == v)
return u;
for (int i = LGN - 1; i >= 0; --i)
{
if(par[u][i] != par[v][i])
{
u = par[u][i];
v = par[v][i];
}
}
return par[u][0];
}
int main()
{
for (int i = 2; i < MAXN; ++i)
{
if(!sieve[i])
{
for (int j = i; j < MAXN; j+=i)
{
factor[j] = i;
sieve[j] = true;
}
}
}
int n,q;
cin>>n>>q;
for (int i = 1; i <= n; ++i)
{
int x;
cin>>x;
cval[i] = x;
vector <pii> pfact = factorise(x);
for (int j = 0; j < pfact.size(); ++j)
{
int p = pfact[j].first, c = pfact[j].second;
to_process[p].push_back(event(0,i,c));
}
}
for (int i = 0; i < n - 1; ++i)
{
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
vector <int> queries;
for (int i = 1; i <= q; ++i)
{
int ty;
cin>>ty;
if(ty == 1)
{
int x,y;
cin>>x>>y;
vector <pii> oldfact = factorise(cval[x]);
for (int j = 0; j < oldfact.size(); ++j)
{
int p = oldfact[j].first;
to_process[p].push_back(event(i,x,0));
}
cval[x] = y;
vector <pii> pfact = factorise(y);
for (int j = 0; j < pfact.size(); ++j)
{
int p = pfact[j].first, c = pfact[j].second;
to_process[p].push_back(event(i,x,c));
}
}
else
{
int u,v,k;
cin>>u>>v>>k;
vector <pii> pfact = factorise(k);
for (int j = 0; j < pfact.size(); ++j)
{
int p = pfact[j].first, c = pfact[j].second;
to_process[p].push_back(event(i,u,v,c));
}
queries.push_back(i);
}
ans[i] = true;
}
dfs(1,0);
for (int j = 1; j < LGN; ++j)
{
for (int i = 1; i <= n; ++i)
{
par[i][j] = par[par[i][j-1]][j-1];
}
}
memset(cval, 0, sizeof cval);
for (int p = 2; p < MAXN; ++p)
{
vector <int> changed;
for (int i = 0; i < to_process[p].size(); ++i)
{
int ty = to_process[p][i].type;
if(ty == 1)
{
int set_to = to_process[p][i].val;
int node = to_process[p][i].v1;
int curr_val = cval[node];
add_val_to_subtree(node,set_to-curr_val);
cval[node] = set_to;
changed.push_back(node);
}
else
{
int u = to_process[p][i].v1, v = to_process[p][i].v2;
int l = lca(u,v);
int path_sum = get_path_val(u) + get_path_val(v) - get_path_val(l) - get_path_val(par[l][0]);
if(path_sum < to_process[p][i].val)
ans[to_process[p][i].index] = false;
}
}
sort(changed.begin(), changed.end());
changed.resize(unique(changed.begin(), changed.end()) - changed.begin());
for (int i = 0; i < changed.size(); ++i)
{
add_val_to_subtree(changed[i], -cval[changed[i]]);
cval[changed[i]] = 0;
}
}
for (int i = 0; i < queries.size(); ++i)
{
if(ans[queries[i]])
cout<<"YES\n";
else
cout<<"NO\n";
}
return 0;
}
0 Comments