Code Submission Evaluation System Login

HIIT Open 2017

Start:2017-05-27 11:00:00
End:2017-05-27 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2017 - Results
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
Language:Java
Status:READY
Result:TIME LIMIT EXCEEDED

Test results

testverdicttime (s)
#1ACCEPTED0.21 / 1.00details
#2ACCEPTED0.17 / 1.00details
#3ACCEPTED0.18 / 1.00details
#4ACCEPTED0.17 / 1.00details
#5TIME LIMIT EXCEEDED-- / 1.00details
#6TIME LIMIT EXCEEDED-- / 1.00details
#7TIME LIMIT EXCEEDED-- / 1.00details
#8TIME LIMIT EXCEEDED-- / 1.00details
#9TIME LIMIT EXCEEDED-- / 1.00details
#10TIME LIMIT EXCEEDED-- / 1.00details
#11TIME LIMIT EXCEEDED-- / 1.00details
#12TIME LIMIT EXCEEDED-- / 1.00details
#13TIME LIMIT EXCEEDED-- / 1.00details
#14TIME LIMIT EXCEEDED-- / 1.00details
#15TIME LIMIT EXCEEDED-- / 1.00details
#16WRONG ANSWER0.16 / 1.00details
#17ACCEPTED0.15 / 1.00details

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

Test details

Test 1

Verdict: ACCEPTED

input
1 0
view   save

correct output
1
view   save

user output
1
view   save

Test 2

Verdict: ACCEPTED

input
2 0
view   save

correct output
1
view   save

user output
1
view   save

Test 3

Verdict: ACCEPTED

input
2 1
2 1
view   save

correct output
2
view   save

user output
2
view   save

Test 4

Verdict: ACCEPTED

input
500 0
view   save

correct output
250
view   save

user output
250
view   save

Test 5

Verdict: TIME LIMIT EXCEEDED

input
500 124750
66 104
50 159
173 457
200 154
416 492
232 191
205 323
201 403
476 348
191 266
239 422
103 442
295 79
191 352
124 451
97 463
353 194
153 82
166 386
...
view   save

correct output
500
view   save

user output
(no output)
view   save

Test 6

Verdict: TIME LIMIT EXCEEDED

input
500 96771
376 390
243 497
417 360
107 80
200 177
107 17
117 486
348 434
262 43
155 79
160 178
247 365
354 101
232 352
414 16
438 80
482 118
484 76
250 183
...
view   save

correct output
413
view   save

user output
(no output)
view   save

Test 7

Verdict: TIME LIMIT EXCEEDED

input
500 106799
96 245
68 62
122 119
460 454
378 409
238 455
262 455
217 35
368 195
318 374
215 496
301 311
255 296
171 95
9 431
284 272
261 258
28 316
489 178
...
view   save

correct output
433
view   save

user output
(no output)
view   save

Test 8

Verdict: TIME LIMIT EXCEEDED

input
500 83550
76 338
111 174
88 142
114 463
416 168
299 273
373 231
495 345
104 414
416 161
141 21
139 348
381 300
290 414
477 487
173 155
161 260
245 300
465 453
...
view   save

correct output
365
view   save

user output
(no output)
view   save

Test 9

Verdict: TIME LIMIT EXCEEDED

input
500 98051
281 60
312 284
270 474
385 224
218 419
201 242
189 271
493 132
344 102
314 408
52 61
21 192
493 486
26 352
227 114
80 296
121 141
457 288
339 410
...
view   save

correct output
410
view   save

user output
(no output)
view   save

Test 10

Verdict: TIME LIMIT EXCEEDED

input
500 86622
5 320
50 107
182 483
385 500
280 389
211 467
423 385
88 310
336 130
44 216
320 489
202 105
217 343
42 398
153 200
351 8
318 61
342 322
113 423
...
view   save

correct output
372
view   save

user output
(no output)
view   save

Test 11

Verdict: TIME LIMIT EXCEEDED

input
500 99445
421 286
392 406
155 290
475 453
316 105
276 310
325 275
428 21
40 137
211 236
194 89
85 259
87 481
342 299
458 132
382 207
447 49
496 242
308 204
...
view   save

correct output
396
view   save

user output
(no output)
view   save

Test 12

Verdict: TIME LIMIT EXCEEDED

input
500 99832
283 149
315 396
264 422
224 388
372 391
333 58
441 470
203 48
323 385
218 366
17 333
176 115
341 107
73 448
380 340
249 165
274 99
345 446
199 399
...
view   save

correct output
410
view   save

user output
(no output)
view   save

Test 13

Verdict: TIME LIMIT EXCEEDED

input
500 116149
446 185
232 35
498 391
189 63
252 474
410 472
132 35
41 475
418 173
343 489
131 39
220 241
333 348
17 333
399 257
70 23
89 488
141 122
171 478
...
view   save

correct output
457
view   save

user output
(no output)
view   save

Test 14

Verdict: TIME LIMIT EXCEEDED

input
500 84757
71 205
286 360
184 486
30 228
230 365
334 386
20 65
131 2
144 189
276 109
225 311
23 242
453 458
414 149
75 70
10 445
66 236
41 356
124 27
...
view   save

correct output
364
view   save

user output
(no output)
view   save

Test 15

Verdict: TIME LIMIT EXCEEDED

input
500 108617
126 250
76 224
449 69
200 63
405 344
143 474
80 131
480 165
135 266
113 369
13 271
287 100
208 167
113 90
145 440
158 427
341 460
404 101
118 373
...
view   save

correct output
439
view   save

user output
(no output)
view   save

Test 16

Verdict: WRONG ANSWER

input
10 20
7 8
1 3
4 8
5 9
2 8
1 7
4 3
10 5
6 5
9 3
10 3
2 4
6 9
1 5
2 3
7 3
5 4
10 7
1 2
...
view   save

correct output
5
view   save

user output
6
view   save

Test 17

Verdict: ACCEPTED

input
10 20
2 9
9 8
4 3
7 3
5 1
5 10
2 1
4 10
2 8
4 7
5 8
4 6
5 9
10 6
5 7
4 9
9 10
5 6
7 10
...
view   save

correct output
5
view   save

user output
5
view   save