Rezultati

Up. imeNalogaJezikRezultatČas oddaje
GrekikiSquad-2017 Škatle Java 100/100OK 20. apr '17 @ 19:26

Test Točke Porabljen spomin Porabljen čas Status
#1 6/6 37,516 MiB 0,000 s OK
#2 6/6 37,891 MiB 0,000 s OK
#3 6/6 40,246 MiB 0,000 s OK
#4 6/6 36,523 MiB 0,000 s OK
#5 6/6 37,684 MiB 0,000 s OK
#6 7/7 36,688 MiB 0,000 s OK
#7 7/7 37,277 MiB 0,000 s OK
#8 7/7 38,367 MiB 0,000 s OK
#9 7/7 37,250 MiB 0,000 s OK
#10 7/7 37,508 MiB 0,000 s OK
#11 7/7 37,004 MiB 0,000 s OK
#12 7/7 39,273 MiB 0,000 s OK
#13 7/7 42,246 MiB 0,000 s OK
#14 7/7 39,766 MiB 0,000 s OK
#15 7/7 40,582 MiB 0,000 s OK

Ocenjevani program (naloga2.java):
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Vector;
class graf{
	box[]nodes;
	int D;
	graf(int a,int b){
		nodes=new box[a];
		D=b;
	}
	boolean put(int a,int b) {
		for(int i=0;i<D;i++) {
			if(nodes[b].q[i]>=nodes[a].q[i]) {
				return false;
			}
		}
		return true;
	}
	void cons() {
		for(int i=0;i<nodes.length;i++) {
			for(int j=0;j<nodes.length;j++) {
				if(i==j) {
					continue;
				}else {
					if(put(i,j)) {
						nodes[i].manjše.add(j);
						nodes[j].večje.add(i);
					}
				}
			}
		}
	}
	int solve() {
		Queue<Integer> bfs=new LinkedList<Integer>();
		for(int i=0;i<nodes.length;i++) {
			if(nodes[i].večje.size()==0) {
				bfs.add(i);
			}
		}
		int[]iskano=new int[nodes.length];
		for(int j=0;j<iskano.length;j++) {
			iskano[j]=nodes[j].večje.size();
		}
		int[]dist=new int[nodes.length];
		while(!bfs.isEmpty()) {
			int id=bfs.poll();
			int d=dist[id];
			for(int i=0;i<nodes[id].manjše.size();i++) {
				int kandidat=nodes[id].manjše.elementAt(i);
				iskano[kandidat]--;
				if(iskano[kandidat]==0) {
					dist[kandidat]=d+1;
					bfs.add(kandidat);
				}
			}
		}
		int max=0;
		for(int i=0;i<dist.length;i++) {
			if(dist[i]>max) {
				max=dist[i];
			}
		}
		return max+1;
	}
	void print() {
		for(int i=0;i<nodes.length;i++) {
			System.out.print(i+" : ");
			for(int j=0;j<nodes[i].manjše.size();j++) {
				System.out.print(nodes[i].manjše.elementAt(j)+" ");
			}
			System.out.println();
		}
	}
}
class box{
	int id;
	Vector<Integer>manjše;
	Vector<Integer>večje;
	int[]q;
	box(String s,int ii){
		id=ii;
		manjše=new Vector<Integer>();
		večje=new Vector<Integer>();
		StringTokenizer st=new StringTokenizer(s);
		q=new int[st.countTokens()];
		for(int i=0;i<q.length;i++) {
			q[i]=Integer.parseInt(st.nextToken());
		}
		Arrays.sort(q);
	}
}
public class naloga2 {
	public static void main(String[] args) throws Exception {
		Scanner sc=new Scanner(System.in);
		StringTokenizer st=new StringTokenizer(sc.nextLine());
		int n=Integer.parseInt(st.nextToken());
		int D=Integer.parseInt(st.nextToken());
		graf g=new graf(n,D);
		for(int i=0;i<n;i++) {
			g.nodes[i]=new box(sc.nextLine(),i);
		}
		g.cons();
		//g.print();
		int r=g.solve();
		System.out.println(r);
	}
	
}