Rezultati

Up. imeNalogaJezikRezultatČas oddaje
snajper Nič nas ne sme presenetiti! Java 0/100Napaka med izvajanjem / ob izhodu (RTE) 19. apr '18 @ 17:42

Test Točke Porabljen spomin Porabljen čas Status
#1 12/12 34,715 MiB 0,000 s OK
#2 0/12 74,414 MiB 0,963 s Napačen odgovor
Tvoj izhod:
​NASLEDNJI
NASLEDNJI
NASLEDNJI
NASLEDNJI
NASLEDNJI
ALAAAARHM
NASLEDNJI
NASLEDNJI
NASLEDNJI
NASLEDNJI
Pravilen izhod:
​NASLEDNJI
NASLEDNJI
NASLEDNJI
NASLEDNJI
NASLEDNJI
NASLEDNJI
NASLEDNJI
NASLEDNJI
NASLEDNJI
NASLEDNJI
#3 12/12 33,449 MiB 0,000 s OK
#4 0/12 161,242 MiB 0,000 s Prekoračen spomin
Stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Nnnp.main(Nnnp.java:54)
#5 13/13 37,926 MiB 0,000 s OK
#6 0/13 158,777 MiB 0,000 s Prekoračen spomin
Stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Nnnp.main(Nnnp.java:54)
#7 0/13 158,785 MiB 0,000 s Prekoračen spomin
Stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Nnnp.main(Nnnp.java:54)
#8 0/13 159,844 MiB 0,000 s Prekoračen spomin
Stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Nnnp.main(Nnnp.java:54)

Ocenjevani program (Nnnp.java):
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

/**
 * Created by snajper on 4/19/18.
 */
public class Nnnp {
    private static final int POVEZAN = 1;
    private static final int NEPOVEZAN = 8;

    private static int n, q;
    private static int[][] matrika;

    private static Mesto[] mesta;
    private static Cesta[] ceste;

    private static HashSet<Integer> visited = new HashSet<>();

    private static class Cesta {
        final int a, b;
        Cesta(final int a, final int b) {
            this.a = a;
            this.b = b;
        }
    }

    private static class Mesto {
        final int index;
        final ArrayList<Mesto> povezanaMesta = new ArrayList<>();
        final ArrayList<Cesta> povezaneCeste = new ArrayList<>();

        Mesto(final int index) {
            this.index = index;
        }
    }

    public static void main(final String[] args) {
        Scanner in = new Scanner(System.in);
        /*try {
            in = new Scanner(new File("./data/nnnp/00.in"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }*/


        // reading
        n = in.nextInt();  // st. mest
        q = in.nextInt();  // st. scenarijev

        matrika = new int[n][n];
        for (int i = 0; i < n; i++) {
            matrika[i][i] = NEPOVEZAN;
        }

        mesta = new Mesto[n];
        for (int i = 0; i < n; i++) {
            mesta[i] = new Mesto(i);
        }

        ceste = new Cesta[n-1];
        for (int i = 0; i < n - 1; i++) {
            final int a = in.nextInt() - 1;
            final int b = in.nextInt() - 1;
            ceste[i] = new Cesta(a, b);
            matrika[a][b] = POVEZAN;
            matrika[b][a] = POVEZAN;

            mesta[a].povezanaMesta.add(mesta[b]);
            mesta[b].povezanaMesta.add(mesta[a]);

            mesta[a].povezaneCeste.add(ceste[i]);
            mesta[b].povezaneCeste.add(ceste[i]);
        }



        // work
        for (int i = 0; i < q; i++) {
            final int n_upornikov = in.nextInt();
            final int[] mesta_uporniki = new int[n_upornikov];
            for (int j = 0; j < n_upornikov; j++) {
                mesta_uporniki[j] = in.nextInt() - 1;
            }

            if (jeAlarm(mesta_uporniki)) {
                System.out.println("ALAAAARHM");
            } else {
                System.out.println("NASLEDNJI");
            }
        }

        in.close();



        /*for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                System.out.print(matrika[x][y] + " ");
            }
            System.out.println();
        }*/
    }

    private static boolean jeAlarm(final int[] mesta_uporniki) {
        if (mesta_uporniki.length <= 1) {
            return true;
        }
        for (int i_upornik_od = 0; i_upornik_od < mesta_uporniki.length; i_upornik_od++) {
            for (int i_upornik_do = i_upornik_od + 1; i_upornik_do < mesta_uporniki.length; i_upornik_do++) {
                visited.clear();
                if (!jePovezan(mesta_uporniki[i_upornik_od], mesta_uporniki[i_upornik_do], mesta_uporniki)) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean jePovezan(final int i_mesta_od, final int i_mesta_do, final int[] mesta_uporniki) {
        if (visited.contains(i_mesta_od)) {
            return false;
        }
        visited.add(i_mesta_od);

        if (matrika[i_mesta_od][i_mesta_do] == POVEZAN) {
            return true;
        }
        for (final Mesto povezanoMesto : mesta[i_mesta_od].povezanaMesta) {
            if (contains(mesta_uporniki, povezanoMesto.index)) {
                if (jePovezan(povezanoMesto.index, i_mesta_do, mesta_uporniki)) {
                    matrika[i_mesta_od][i_mesta_do] = POVEZAN;
                    matrika[i_mesta_do][i_mesta_od] = POVEZAN;
                    return true;
                }
            }
        }
        matrika[i_mesta_od][i_mesta_do] = NEPOVEZAN;
        matrika[i_mesta_do][i_mesta_od] = NEPOVEZAN;
        return false;
    }

    private static boolean contains(final int[] array, final int value) {
        /*for (int i : array) {
            if (i == value) {
                return true;
            }
        }*/
        for (int i = 0; i < array.length; i++) {
            if (array[i] == value) {
                return true;
            }
        }
        return false;
    }
}