Code Submission Evaluation System Login

CSES - HIIT Open 2017

HIIT Open 2017

Contest start:2017-05-27 11:00:00
Contest end:2017-05-27 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard


History
2017-05-27 15:58:17
2017-05-27 15:55:55
2017-05-27 15:52:14
2017-05-27 15:48:31
2017-05-27 15:23:51
2017-05-27 14:23:15
Task:Factory
Sender:HIIT AND RUN
Submission time:2017-05-27 15:58:17
Status:READY
Result:TIME LIMIT EXCEEDED

Show test data

Code

//package hiit;

import java.util.*;

public class F {
	
	static HashSet<Integer>[] downLine;
	static HashSet<Integer>[] upLine;
	static int[] children;
	static int[] parents;
	static PriorityQueue<Job> q;
	static ArrayDeque<Integer> unlockableSingles;
	static ArrayDeque<Integer> unlockableSinglesAdditions;
	static HashSet<Integer> notDone;

	public static void main(String[] args) {
		int time = 0;
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		children = new int[n+1];
		parents = new int[n+1];
		downLine = new HashSet[n+1];
		upLine = new HashSet[n+1];
		for (int i=1; i<=n; i++) {
			downLine[i] = new HashSet();
			upLine[i] = new HashSet();
		}
		for (int i=1; i<=m; i++) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			children[a]++;
			parents[b]++;
			downLine[a].add(b);
			upLine[b].add(a);
		}
		
		unlockableSingles = new ArrayDeque<>();
		unlockableSinglesAdditions = new ArrayDeque<>();
		notDone = new HashSet<>();
		for (int i=1; i<=n; i++) {
			if (parents[i] == 0 && children[i] == 0) unlockableSingles.add(i);
			else notDone.add(i);
		}
		while (!notDone.isEmpty() || !unlockableSingles.isEmpty()) {
			//System.out.println("NOTDONE ");
			//System.out.println(notDone);
			time++;
			HashSet<Integer> secondBestChoiceUnlockableParents = null;
			HashSet<Integer> bestChoiceUnlockableParents = null;
			int bestVal = 0;
			
			for (Integer i : notDone) {
				HashSet<Integer> immediatelyUnlockableParents = new HashSet<>();
				for (Integer dad : upLine[i]) {
					if (parents[dad] > 0) continue;
					immediatelyUnlockableParents.add(dad);
					if (immediatelyUnlockableParents.size() == 2) break;
				}
				int val = immediatelyUnlockableParents.size();
				if (val >= bestVal) {
					bestVal = val;
					secondBestChoiceUnlockableParents = bestChoiceUnlockableParents;
					bestChoiceUnlockableParents = immediatelyUnlockableParents;
				}
				if (val >= 2) {
					break;
				}
			}
			int counter = 0;
			if (bestChoiceUnlockableParents != null) {
				for (Integer node : bestChoiceUnlockableParents) {
					unlock(node);
					counter++;
				}
			}
			if (counter < 2 && secondBestChoiceUnlockableParents != null) {
				for (Integer node : secondBestChoiceUnlockableParents) {
					if (bestChoiceUnlockableParents.contains(node)) continue;
					unlock(node);
					counter++;
				}
			}
			while (counter < 2 && unlockableSingles.size() > 0) {
				int node = unlockableSingles.poll();
				unlock(node);
				counter++;
			}
			
			for (Integer addition : unlockableSinglesAdditions) {
				unlockableSingles.add(addition);
			}
			unlockableSinglesAdditions.clear();
		}
		
		System.out.println(time);
	}
	
	static void unlock(Integer node) {
		//System.out.println("Unlocing " + node);
		notDone.remove(node);
		for (Integer child : downLine[node]) {
			parents[child]--;
			if (parents[child] == 0 && children[child] == 0) unlockableSinglesAdditions.add(child);
			upLine[child].remove(node);
		}
	}
	
	

}

class Job implements Comparable<Job> {
	int node;
	int children;
	
	public Job(int node, int children) {
		this.node = node;
		this.children = children;
	}

	@Override
	public int compareTo(Job o) {
		if (this.children > o.children) return -1;
		if (this.children < o.children) return 1;
		return 0;
	}
	
}