Hi,
I have been trying to submit this problem only to be stopped by NZEC error. It gives correct output on my system. Any pointers as to what might i be doing wrong.Here’s my code:
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
class SpojQtreeTwo {
public static void main(String[] args) throws IOException {
Scanner sc=new Scanner(System.in);
int t=Integer.parseInt(sc.nextLine());
while(t–>0)
{
int n=Integer.parseInt(sc.nextLine());
graph g=new graph(n);
for (int i = 1; i <=n; i++) {
g.addVertex(new vertex(i));
}
for (int i = 0; i < n-1; i++) {
String p=sc.nextLine();
String []sp=p.split(" “);
int s=Integer.parseInt(sp[0]);
int d=Integer.parseInt(sp[1]);
int wt=Integer.parseInt(sp[2]);
g.addEdge(g.vertexList.get(s-1),g.vertexList.get(d-1), wt);
}
String s=sc.nextLine();
while(!“DONE”.equals(s))
{
g.dfsEulerTourStyle(g.vertexList.get(0));
g.produceOccurence();
String []sp=s.split(” “);
if(“DIST”.equals(sp[0]))
{
int source=Integer.parseInt(sp[1]);
int destination=Integer.parseInt(sp[2]);
queryPos ap=new queryPos(source,destination);
System.out.println(g.returnDist(ap, n));
}
else
{
int source=Integer.parseInt(sp[1]);
int destination=Integer.parseInt(sp[2]);
int k=Integer.parseInt(sp[3]);
queryPos ap=new queryPos(source,destination);
g.returnDist(ap, n);
System.out.println(g.path.get(k-1));
}
s=sc.nextLine();
}
if(t>0)
{
sc.nextLine();
System.out.println(”");
}
}
}
}
class graph // it is a non-directed and weighted graph
{
public int [][]ar;
public ArrayList vertexList,eulerTraversal;
public Map<vertex,Integer> firstOccurence;
public Map<Integer,vertex> revFirstOccurence;
public ArrayList path;
public int numOfVertices;
public graph(int size) {
numOfVertices=size;
ar=new int[numOfVertices][numOfVertices];
for (int i = 0; i < numOfVertices; i++) {
Arrays.fill(ar[i],Integer.MAX_VALUE);
}
//adjList=new ArrayList<>();
vertexList=new ArrayList<>();
eulerTraversal=new ArrayList<>();
firstOccurence=new HashMap<>();
revFirstOccurence=new HashMap<>();
path=new ArrayList<>();
}
public void addVertex(vertex vert)
{
vertexList.add(vert);
// numOfVertices++;
}
public void addEdge(vertex source,vertex destination,int weight)
{
ar[source.label-1][destination.label-1]=weight;
ar[destination.label-1][source.label-1]=weight;
}
public int getEdgeWeight(vertex source,vertex destination)
{
return ar[source.label-1][destination.label-1];
}
public int getAdjacent(vertex v)
{
for (int i = 0; i < vertexList.size(); i++) {
if(i!=v.label-1)
{
if(ar[v.label-1][i]!=Integer.MAX_VALUE && !vertexList.get(i).visited)
{
vertexList.get(i).visited=true;
return i;
}
}
}
return -1;
}
public void dfsEulerTourStyle(vertex root)
{
Stack st=new Stack<>();
st.add(root);
root.visited=true;
int orderNum=0;
while(!st.isEmpty())
{
eulerTraversal.add(st.peek());
st.peek().level_number=(st.peek().level_number==Integer.MAX_VALUE)?orderNum++:st.peek().level_number;
int p=getAdjacent(st.peek());
if(p!=-1)
st.add(vertexList.get§);
else
st.pop();
}
}
public void produceOccurence()
{
for (int i = 0; i < eulerTraversal.size(); i++) {
if(!firstOccurence.containsKey(eulerTraversal.get(i)))
firstOccurence.put(eulerTraversal.get(i),i);
revFirstOccurence.put(i,eulerTraversal.get(i));
}
}
public queryPos returnIndexes(vertex a,vertex b)
{
return new queryPos(firstOccurence.get(a),firstOccurence.get(b));
}
public int rmqQuery(queryPos qp,int n)
{
int startOfRange=qp.a;
int endOfRange=qp.b;
int minLevel=eulerTraversal.get(startOfRange).level_number,minLevelPos=startOfRange;
for (int i = startOfRange+1; i <=endOfRange ; i++) {
if(eulerTraversal.get(i).level_number<minLevel)
{
minLevel=eulerTraversal.get(i).level_number;
minLevelPos=i;
}
}
return minLevelPos;
}
public long returnDist(queryPos qp,int n)
{
qp=returnIndexes(vertexList.get(qp.a-1),vertexList.get(qp.b-1));
int vindex=rmqQuery(qp, n);
//System.out.println("vindex= "+vindex);
long sum=0;
Set visited=new HashSet<>();
for (int i = qp.a; i <vindex;) {
path.add(revFirstOccurence.get(i).label);
i++;
}
for (int i = vindex; i <=qp.b;i++) {
path.add(revFirstOccurence.get(i).label);
}
// calculating the sum now
Set st=new HashSet<>();
int []posArr=new int[n+1];
Arrays.fill(posArr,-1);
int j=0;
while(j<path.size()) {
if(!st.contains(path.get(j)))
{
st.add(path.get(j));
posArr[path.get(j)]=j;
}
else
{
int fpos=posArr[path.get(j)];
int count=(j-fpos);
for(int i=j;i>fpos;i–){
path.remove(i);
}
if(j>=path.size())
break;
j-=(j-path.get(j));
}
j+=1;
}
for (int i = 0; i < path.size()-1; i++) {
sum+=ar[path.get(i)-1][path.get(i+1)-1];
}
return sum;
}
}
class queryPos
{
public int a,b;
public queryPos(int a, int b) {
this.a = a;
this.b = b;
}
}
class vertex
{
public int label;
public int level_number;
public boolean visited;
public vertex(int label) {
this.label = label;
this.level_number=Integer.MAX_VALUE;
this.visited=false;
}
}