CSES - HIIT Open 2017 - Results
 Task: Factory Sender: HIIT AND RUN Submission time: 2017-05-27 15:58:17 Language: Java Status: READY Result: TIME LIMIT EXCEEDED
Test results
testverdicttime
#1ACCEPTED0.21 sdetails
#2ACCEPTED0.17 sdetails
#3ACCEPTED0.18 sdetails
#4ACCEPTED0.17 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.15 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;
static ArrayDeque<Integer> unlockableSingles;
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]++;
}

unlockableSingles = new ArrayDeque<>();
notDone = new HashSet<>();
for (int i=1; i<=n; i++) {
if (parents[i] == 0 && children[i] == 0) unlockableSingles.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 (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++;
}

}
}

System.out.println(time);
}

static void unlock(Integer node) {
//System.out.println("Unlocing " + node);
notDone.remove(node);
for (Integer child : downLine[node]) {
parents[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;
}

}```

### 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

Verdict:

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

correct output
500

user output
(empty)

Verdict:

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

correct output
413

user output
(empty)

Verdict:

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

correct output
433

user output
(empty)

Verdict:

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

correct output
365

user output
(empty)

Verdict:

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

correct output
410

user output
(empty)

Verdict:

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

correct output
372

user output
(empty)

Verdict:

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

correct output
396

user output
(empty)

Verdict:

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

correct output
410

user output
(empty)

Verdict:

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

correct output
457

user output
(empty)

Verdict:

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

correct output
364

user output
(empty)

Verdict:

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

correct output
439

user output
(empty)

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