oj.uz

Submission #300332

# Submission time Handle Problem Language Result Execution time Memory
300332 2020-09-17T05:31:36 Z mythos Connecting Supertrees (IOI20_supertrees) Java 11
19 / 100
 502 ms 59284 KB 
import java.util.ArrayList;
import java.util.Arrays;

class supertrees {
	int n;
	int construct(int[][] p) {
		n = p.length;
		boolean used[] = new boolean[n];
		int[][] b = new int[n][n];
		int[] parent = new int[n];
		for (int i=0; i<n; i++) {
			ArrayList<Integer> l = new ArrayList<>();
			if(!used[i]) {
				for(int j=0; j<n; j++) {
					if(p[i][j]==2) {
						l.add(j);
						used[i] = true;
						used[j] = true;
					}
				}
				if(l.size() == 1) return 0;
			
				if(l.size() >= 2) {
					for(int j=0; j+1<l.size(); j++) {
						b[l.get(j)][l.get(j+1)] = 1;
						b[l.get(j+1)][l.get(j)] = 1;
					}
					b[l.get(0)][i] = 1;
					b[i][l.get(0)] = 1;
					b[l.get(l.size()-1)][i] = 1;
					b[i][l.get(l.size()-1)] = 1;
				}
			}
		}
		
		for(int i=0; i<n; i++) {
			parent[i] = i;
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<i; j++) {
				if(p[i][j]==2) {
					parent[j] = i;
				}
			}
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(p[i][j]==2 && parent[i]!=parent[j]) {
					return 0;
				}
				if(p[i][j]==0 && parent[i]==parent[j]) {
					return 0;
				}
			}
		}

		grader.build(b);
		return 1;
	}
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 10208 KB Output is correct
2 Incorrect 78 ms 10296 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 10208 KB Output is correct
2 Incorrect 78 ms 10296 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10248 KB Output is correct
2 Correct 81 ms 10316 KB Output is correct
3 Correct 77 ms 10228 KB Output is correct
4 Correct 78 ms 10088 KB Output is correct
5 Correct 79 ms 10232 KB Output is correct
6 Correct 83 ms 10104 KB Output is correct
7 Correct 79 ms 10216 KB Output is correct
8 Correct 190 ms 15324 KB Output is correct
9 Correct 431 ms 56532 KB Output is correct
10 Correct 80 ms 10092 KB Output is correct
11 Correct 78 ms 10232 KB Output is correct
12 Correct 202 ms 15304 KB Output is correct
13 Correct 418 ms 56452 KB Output is correct
14 Correct 80 ms 10336 KB Output is correct
15 Correct 79 ms 10216 KB Output is correct
16 Correct 98 ms 11004 KB Output is correct
17 Correct 152 ms 19720 KB Output is correct
18 Correct 91 ms 10216 KB Output is correct
19 Correct 79 ms 10236 KB Output is correct
20 Correct 78 ms 10104 KB Output is correct
21 Correct 352 ms 25604 KB Output is correct
22 Correct 432 ms 56236 KB Output is correct
23 Correct 425 ms 56772 KB Output is correct
24 Correct 502 ms 59284 KB Output is correct
25 Correct 145 ms 19408 KB Output is correct
26 Correct 156 ms 19796 KB Output is correct
27 Correct 436 ms 56036 KB Output is correct
28 Correct 428 ms 56624 KB Output is correct
29 Correct 157 ms 19412 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10360 KB Output is correct
2 Correct 81 ms 10088 KB Output is correct
3 Incorrect 78 ms 10104 KB Too few ways to get from 1 to 2, should be 1 found 0
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 10208 KB Output is correct
2 Incorrect 78 ms 10296 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 10208 KB Output is correct
2 Incorrect 78 ms 10296 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -