Rezultati

Up. imeNalogaJezikRezultatČas oddaje
avokado-2018 Nič nas ne sme presenetiti! Java 0/100Napaka med izvajanjem / ob izhodu (RTE) 19. apr '18 @ 16:43

Test Točke Porabljen spomin Porabljen čas Status
#1 12/12 35,902 MiB 0,000 s OK
#2 12/12 81,027 MiB 1,880 s OK
#3 12/12 38,672 MiB 0,000 s OK
#4 0/12 86,113 MiB 1,107 s Program je končal z neničelno kodo
Stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 100000
	at graph.dfs(nnnp.java:96)
	at nnnp.main(nnnp.java:38)
#5 13/13 36,320 MiB 0,000 s OK
#6 0/13 102,871 MiB 3,721 s Prekoračen čas
Stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 100000
	at nnnp.main(nnnp.java:35)
#7 0/13 103,941 MiB 5,424 s Prekoračen čas
#8 0/13 89,176 MiB 0,606 s Program je končal z neničelno kodo
Stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 100000
	at graph.dfs(nnnp.java:96)
	at nnnp.main(nnnp.java:38)

Ocenjevani program (nnnp.java):
import java.awt.font.GraphicAttribute;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.Vector;

public class nnnp {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br  =new BufferedReader(new InputStreamReader(System.in));
		String[] prva = br.readLine().split(" ");
		
		int n = Integer.parseInt(prva[0]);
		int q = Integer.parseInt(prva[1]);
		
		graph g = new graph(n+1);
		
		for (int i = 1; i < n; i++){
			prva = br.readLine().split(" ");
			
			int u = Integer.parseInt(prva[0]);
			int v = Integer.parseInt(prva[1]);
			
			g.addEdge(u, v);
			
		}
		
		for (int i = 0; i < q; i++){
			prva = br.readLine().split(" ");
			
			int u = Integer.parseInt(prva[0]);
			int[] mesta = new int[100000];

			for (int j = 0; j < u; j++){
				mesta[Integer.parseInt(prva[j+1])] = 1;
			}
			g.mesta(mesta, u);
			if (g.dfs(Integer.parseInt(prva[1]))){
				System.out.println("ALAAAARHM");
			} else {
				System.out.println("NASLEDNJI");
			}
		}
		
	}
	
}

class graph{
	Vector<Vector<Integer>> neighbors;
	int n;
	int[] mesta = new int[100000];
	int stevec = 0;
	
	public graph(int n){
		this.n = n;
		neighbors = new Vector<Vector<Integer>>();
		for (int i = 0; i < n; i++){
			neighbors.add(new Vector<Integer>());
		}
	}
	
	public void addEdge(int u, int v){
		neighbors.get(u).add(v);
		neighbors.get(v).add(u);
	}
	
	public void mesta(int[] mesta, int stevec){
		this.mesta = mesta;
		this.stevec = stevec;
	}
	
	public boolean dfs(int start){
		
		boolean[] proccessed = new boolean[n];
		boolean[] discovered = new boolean[n];
		
		for (int i = 0; i < n; i++){
			proccessed[i] = false;
			discovered[i] = false;
		}
		
		Stack<Integer> q = new Stack<Integer>();
		q.add(start);
		stevec--;
		discovered[start] = true;
		
		while(!q.empty()){
			int v = q.pop();
			proccessed[v] = true;
			
			for (int i = 0; i < neighbors.get(v).size(); i++) {
				int u = neighbors.get(v).get(i);

				if (!discovered[u]){
					if(mesta[u] == 1) {
						q.push(u);
						mesta[u] = 0;
						stevec--;
					}
					discovered[u] = true;
				}
			}
		}
		if (stevec == 0){
			return true;
		}
		return false;
	}
	
}