CSES - HIIT Open 2017 - Results
Submission details
Task:Factory
Sender:HIIT AND RUN
Submission time:2017-05-27 15:23:51 +0300
Language:Java
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.16 sdetails
#2ACCEPTED0.19 sdetails
#3ACCEPTED0.18 sdetails
#4ACCEPTED0.27 sdetails
#5--details
#6--details
#7--details
#8--details
#9--details
#10--details
#11--details
#12--details
#13--details
#14--details
#15--details
#160.16 sdetails
#17ACCEPTED0.17 sdetails

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;

	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);
		}
		
		HashSet<Integer> notDone = new HashSet<>();
		for (int i=1; i<=n; i++) {
			notDone.add(i);
		}
		while (!notDone.isEmpty()) {
			time++;
			HashSet<Integer> unlockableSingles = new HashSet<>();
			HashSet<Integer> secondBestChoiceUnlockableParents = null;
			HashSet<Integer> bestChoiceUnlockableParents = null;
			int bestVal = 0;
			for (Integer i : notDone) {
				HashSet<Integer> immediatelyUnlockableParents = new HashSet<>();
				if (downLine[i].size() == 0 && upLine[i].size() == 0) unlockableSingles.add(i);
				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);
					notDone.remove(node);
					counter++;
				}
			}
			if (counter < 2 && secondBestChoiceUnlockableParents != null) {
				for (Integer node : secondBestChoiceUnlockableParents) {
					if (bestChoiceUnlockableParents.contains(node)) continue;
					unlock(node);
					notDone.remove(node);
					counter++;
				}
			}
			if (counter < 2 && unlockableSingles.size() > 0) {
				for (Integer node : unlockableSingles) {
					unlock(node);
					notDone.remove(node);
					counter++;
					if (counter == 2) break;
				}
			}
		}
		
		
		/*
		q = new PriorityQueue<>();
		for (int i=1; i<=n; i++) {
			if (parents[i] == 0) {
				q.add(new Job(i, children[i]));
			}
		}
		
		
		while (!q.isEmpty()) {
			time++;
			Job wait = q.poll();
			if (!q.isEmpty()) work(q.poll());
			work(wait);
		}*/
		
		System.out.println(time);
	}
	
	static void unlock(Integer node) {
		//System.out.println("Unlocing " + node);
		for (Integer child : downLine[node]) {
			parents[child]--;
			upLine[child].remove(node);
		}
	}
	
	static void work(Job job) {
		for (Integer child : downLine[job.node]) {
			parents[child]--;
			if (parents[child] == 0) {
				q.add(new Job(child, children[child]));
			}
		}
	}
	
	

}

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;
	}
	
}

Test details

Test 1

Verdict: ACCEPTED

input
1 0

correct output
1

user output
1

Test 2

Verdict: ACCEPTED

input
2 0

correct output
1

user output
1

Test 3

Verdict: ACCEPTED

input
2 1
2 1

correct output
2

user output
2

Test 4

Verdict: ACCEPTED

input
500 0

correct output
250

user output
250

Test 5

Verdict:

input
500 124750
66 104
50 159
173 457
200 154
...

correct output
500

user output
(empty)

Test 6

Verdict:

input
500 96771
376 390
243 497
417 360
107 80
...

correct output
413

user output
(empty)

Test 7

Verdict:

input
500 106799
96 245
68 62
122 119
460 454
...

correct output
433

user output
(empty)

Test 8

Verdict:

input
500 83550
76 338
111 174
88 142
114 463
...

correct output
365

user output
(empty)

Test 9

Verdict:

input
500 98051
281 60
312 284
270 474
385 224
...

correct output
410

user output
(empty)

Test 10

Verdict:

input
500 86622
5 320
50 107
182 483
385 500
...

correct output
372

user output
(empty)

Test 11

Verdict:

input
500 99445
421 286
392 406
155 290
475 453
...

correct output
396

user output
(empty)

Test 12

Verdict:

input
500 99832
283 149
315 396
264 422
224 388
...

correct output
410

user output
(empty)

Test 13

Verdict:

input
500 116149
446 185
232 35
498 391
189 63
...

correct output
457

user output
(empty)

Test 14

Verdict:

input
500 84757
71 205
286 360
184 486
30 228
...

correct output
364

user output
(empty)

Test 15

Verdict:

input
500 108617
126 250
76 224
449 69
200 63
...

correct output
439

user output
(empty)

Test 16

Verdict:

input
10 20
7 8
1 3
4 8
5 9
...

correct output
5

user output
6

Test 17

Verdict: ACCEPTED

input
10 20
2 9
9 8
4 3
7 3
...

correct output
5

user output
5