We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
can anyone tell why this code is givin runtime error on few test cases
import java.util.;
import java.io.;
class Solution{
static PrintWriter out = new PrintWriter(System.out);
static int N =60000, LOGN = 20;
static int n,q,ptr,chainNo;
static int subSize[] = new int[N];
static int depth[] = new int[N];
static int st[] = new int[4*N];
static int chainInd[] = new int[N];
static int chainHead[] = new int[N];
static int base[] = new int[N];
static int posInBase[] = new int[N];
static int node[] = new int[N];
static int P[][] = new int[LOGN][N];
static LinkedList g[] = new LinkedList[N];
static int LCA(int x , int y){
if(depth[x] < depth[y]){
int t =x;
x=y;
y=t;
}
int lg = 1; for(;(1<= 0 ; i--)
if(depth[x] - (1<= depth[y])
x = P[i][x];
if(x == y)return x;
for(int i = lg ; i >= 0 ; i--)
if(P[i][x] != -1 && P[i][x] != P[i][y]){
x = P[i][x];
y = P[i][y];
}
return P[0][x];
}
static void build() {
for (int i = n - 1; i > 0; --i)
st[i] = st[i<<1] +st[i<<1|1];
}
static void modify(int p, int value) {
for (st[p += n] = value; p > 1; p >>= 1)
st[p>>1] = st[p] + st[p^1];
}
static int query(int l, int r) { // max on interval [l, r)
int res = 0 ;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if ((l&1)==1) res = res+st[l++];
if ((r&1)==1) res = res+st[--r];
}
return res;
}
static void dfs(int a,int p,int level){
depth[a]=level;
subSize[a]=1;
P[0][a]=p;
for(Integer I : g[a])
if(I!=p){
dfs(I,a,level+1);
subSize[a]+=subSize[I];
}
}
chainInd[curNode]=chainNo;
posInBase[curNode]=ptr;
node[posInBase[curNode]]=curNode;
base[ptr++]=0;
int sc=-1;
for(Integer I : g[curNode])
if(I!=p){
if(sc==-1 || (sc!=-1 && subSize[sc]<subSize[I]))
sc= I;
}
if(sc!=-1)
hld(sc,curNode);
for(Integer I : g[curNode])
if(I!=p&&I!=sc){
chainNo++;
hld(I,curNode);
}
}
public static void main(String[] args){
Arrays.fill(chainHead , -1);
n = ni();
q = ni();
int value[] = new int[n];
// st = new int[2*n];
for(int i=0;i
for(int i=1;i<=q;i++) {
int type = ni();
if(type == 1) {
int u = ni();
int x = ni();
value[u]=x;
update(u , x);
}
else {
int u = ni();
int v = ni();
int lca = LCA(u,v);
int ans = query_up(u,lca) + query_up(v,lca)-value[lca];
System.out.println(ans);
}
}
// out.flush();
}
static FastReader sc=new FastReader();
static int ni(){
int x = sc.nextInt();
return(x);
}
static long nl(){
long x = sc.nextLong();
return(x);
}
static String n(){
String str = sc.next();
return(str);
}
static String ns(){
String str = sc.nextLine();
return(str);
}
static double nd(){
double d = sc.nextDouble();
return(d);
}
static class FastReader
{
BufferedReader br;
StringTokenizer st;
Lazy White Falcon
You are viewing a single comment's thread. Return to all comments →
can anyone tell why this code is givin runtime error on few test cases
import java.util.; import java.io.; class Solution{ static PrintWriter out = new PrintWriter(System.out); static int N =60000, LOGN = 20; static int n,q,ptr,chainNo; static int subSize[] = new int[N]; static int depth[] = new int[N]; static int st[] = new int[4*N]; static int chainInd[] = new int[N]; static int chainHead[] = new int[N]; static int base[] = new int[N]; static int posInBase[] = new int[N]; static int node[] = new int[N]; static int P[][] = new int[LOGN][N]; static LinkedList g[] = new LinkedList[N];
static int LCA(int x , int y){ if(depth[x] < depth[y]){ int t =x; x=y; y=t; } int lg = 1; for(;(1<= 0 ; i--) if(depth[x] - (1<= depth[y]) x = P[i][x]; if(x == y)return x; for(int i = lg ; i >= 0 ; i--) if(P[i][x] != -1 && P[i][x] != P[i][y]){ x = P[i][x]; y = P[i][y]; } return P[0][x]; } static void build() {
for (int i = n - 1; i > 0; --i) st[i] = st[i<<1] +st[i<<1|1]; }
static void modify(int p, int value) { for (st[p += n] = value; p > 1; p >>= 1) st[p>>1] = st[p] + st[p^1]; }
static int query(int l, int r) { // max on interval [l, r) int res = 0 ; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if ((l&1)==1) res = res+st[l++]; if ((r&1)==1) res = res+st[--r]; } return res; } static void dfs(int a,int p,int level){ depth[a]=level; subSize[a]=1; P[0][a]=p; for(Integer I : g[a]) if(I!=p){ dfs(I,a,level+1); subSize[a]+=subSize[I]; } }
static int query_up(int u,int v){
int uchain,vchain=chainInd[v],ret=0; while(1>0){ uchain=chainInd[u]; if(uchain==vchain){ ret=ret+query(posInBase[v],posInBase[u]+1); break; } else{ ret=ret+query(posInBase[chainHead[uchain]],posInBase[u]+1);
u=P[0][chainHead[uchain]]; } } return ret; }
static void update(int node , int val) { int pos = posInBase[node]; modify( pos,val); }
static void hld(int curNode,int p){ if(chainHead[chainNo]==-1) chainHead[chainNo]=curNode;
}
public static void main(String[] args){ Arrays.fill(chainHead , -1); n = ni(); q = ni(); int value[] = new int[n]; // st = new int[2*n]; for(int i=0;i for(int i=1;i<=q;i++) { int type = ni(); if(type == 1) { int u = ni(); int x = ni(); value[u]=x; update(u , x); } else { int u = ni(); int v = ni(); int lca = LCA(u,v); int ans = query_up(u,lca) + query_up(v,lca)-value[lca]; System.out.println(ans); } } // out.flush(); } static FastReader sc=new FastReader();
static class FastReader { BufferedReader br; StringTokenizer st;
}