oj.uz

Submission #303144

# Submission time Handle Problem Language Result Execution time Memory
303144 2020-09-19T23:06:20 Z llaki Connecting Supertrees (IOI20_supertrees) Java 11
21 / 100
 480 ms 57848 KB 
import java.util.ArrayList;
import java.util.Arrays;

public class supertrees {
    int construct(int[][] p) {
        int n = p.length;
        if (areAllOnes(p)) {
            return constructForAllOnes(n);
        }
        if (areAllAtMostOnes(p)) {
            return constructForAllAtMostOnes(p, n);
        }
        if (areAllZeroOrTwo(p)) {
            return constructAllZeroOrTwo(p, n);
        }
        int[][] answer = new int[n][n];

        grader.build(answer);
        return 1;
    }

    int constructAllZeroOrTwo(int[][] p, int n) {
        int[] comp = new int[n];
        int[][] b = new int[n][n];
        Arrays.fill(comp, -1);
        int c = 0;
        for (int i = 0; i < n; i++) {
            if (comp[i] != -1) continue;
            comp[i] = c;
            for (int j = i + 1; j < n; j++) {
                if (p[i][j] > 0) {
                    if (comp[j] != -1) return 0;
                    comp[j] = c;
                }
            }
            c++;
        }
        for (int i = 0; i < n; i++) {
            if (p[i][i] != 1) return 0;
            for (int j = 0; j < n; j++) {
                if (p[i][j] > 0 && comp[i] != comp[j]) return 0;
                if (p[i][j] == 0 && comp[i] == comp[j]) return 0;
            }
        }
        ArrayList<Integer>[] C = new ArrayList[c];
        for (int i = 0; i < c; i++) {
            C[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            C[comp[i]].add(i);
        }
        for (int i = 0; i < c; i++) {
            if (C[i].size() == 1) continue;
            if (C[i].size() == 2) return 0;
            for (int j = 1; j < C[i].size() - 1; j++) {
                b[C[i].get(j)][C[i].get(j + 1)] = 1;
                b[C[i].get(j + 1)][C[i].get(j)] = 1;
            }
            b[C[i].get(0)][C[i].get(1)] = 1;
            b[C[i].get(1)][C[i].get(0)] = 1;
            b[C[i].get(0)][C[i].get(C[i].size() - 1)] = 1;
            b[C[i].get(C[i].size() - 1)][C[i].get(1)] = 1;
        }
        grader.build(b);
        return 1;
    }

    int constructForAllAtMostOnes(int[][] p, int n) {
        int[] comp = new int[n];
        int[][] b = new int[n][n];
        Arrays.fill(comp, -1);
        int c = 0;
        for (int i = 0; i < n; i++) {
            if (comp[i] != -1) continue;
            comp[i] = c;
            for (int j = i + 1; j < n; j++) {
                if (p[i][j] > 0) {
                    if (comp[j] != -1) return 0;
                    comp[j] = c;
                }
            }
            c++;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (p[i][j] > 0 && comp[i] != comp[j]) return 0;
                if (p[i][j] == 0 && comp[i] == comp[j]) return 0;
            }
        }
        ArrayList<Integer>[] C = new ArrayList[c];
        for (int i = 0; i < c; i++) {
            C[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            C[comp[i]].add(i);
        }
        for (int i = 0; i < c; i++) {
            for (int j = 0; j < C[i].size() - 1; j++) {
                b[C[i].get(j)][C[i].get(j + 1)] = 1;
                b[C[i].get(j + 1)][C[i].get(j)] = 1;
            }
        }
        grader.build(b);
        return 1;
    }

    boolean areAllZeroOrTwo(int[][] p) {
        for (int i = 0; i < p.length; i++) {
            for (int j = 0; j < p[i].length; j++) {
                if (p[i][j] % 2 == 1) return false;
            }
        }
        return true;
    }

    boolean areAllAtMostOnes(int[][] p) {
        for (int i = 0; i < p.length; i++) {
            for (int j = 0; j < p[i].length; j++) {
                if (p[i][j] > 1) return false;
            }
        }
        return true;
    }

    boolean areAllOnes(int[][] p) {
        for (int i = 0; i < p.length; i++) {
            for (int j = 0; j < p[i].length; j++) {
                if (p[i][j] != 1) return false;
            }
        }
        return true;
    }

    int constructForAllOnes(int n) {
        int[][] res = new int[n][n];
        for (int i = 0; i < n - 1; i++) {
            res[i][i + 1] = 1;
            res[i + 1][i] = 1;
        }
        grader.build(res);
        return 1;
    }
}

Compilation message

Note: supertrees.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 10344 KB Output is correct
2 Correct 75 ms 10224 KB Output is correct
3 Correct 79 ms 10344 KB Output is correct
4 Correct 80 ms 10220 KB Output is correct
5 Correct 94 ms 10240 KB Output is correct
6 Correct 187 ms 15608 KB Output is correct
7 Correct 394 ms 56804 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 10344 KB Output is correct
2 Correct 75 ms 10224 KB Output is correct
3 Correct 79 ms 10344 KB Output is correct
4 Correct 80 ms 10220 KB Output is correct
5 Correct 94 ms 10240 KB Output is correct
6 Correct 187 ms 15608 KB Output is correct
7 Correct 394 ms 56804 KB Output is correct
8 Correct 78 ms 10212 KB Output is correct
9 Correct 79 ms 10344 KB Output is correct
10 Correct 81 ms 10344 KB Output is correct
11 Correct 81 ms 10472 KB Output is correct
12 Correct 189 ms 15332 KB Output is correct
13 Correct 431 ms 55756 KB Output is correct
14 Correct 77 ms 10100 KB Output is correct
15 Correct 76 ms 10232 KB Output is correct
16 Correct 93 ms 11128 KB Output is correct
17 Correct 136 ms 19120 KB Output is correct
18 Correct 82 ms 9976 KB Output is correct
19 Correct 79 ms 10308 KB Output is correct
20 Correct 339 ms 26448 KB Output is correct
21 Correct 413 ms 56240 KB Output is correct
22 Correct 407 ms 56640 KB Output is correct
23 Correct 409 ms 56420 KB Output is correct
24 Correct 480 ms 57848 KB Output is correct
25 Correct 155 ms 19304 KB Output is correct
26 Correct 141 ms 19192 KB Output is correct
27 Correct 435 ms 56744 KB Output is correct
28 Correct 425 ms 57216 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10228 KB Output is correct
2 Correct 76 ms 10360 KB Output is correct
3 Correct 79 ms 10260 KB Output is correct
4 Incorrect 79 ms 10436 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 10344 KB Output is correct
2 Correct 75 ms 10224 KB Output is correct
3 Correct 79 ms 10344 KB Output is correct
4 Correct 80 ms 10220 KB Output is correct
5 Correct 94 ms 10240 KB Output is correct
6 Correct 187 ms 15608 KB Output is correct
7 Correct 394 ms 56804 KB Output is correct
8 Correct 78 ms 10212 KB Output is correct
9 Correct 79 ms 10344 KB Output is correct
10 Correct 81 ms 10344 KB Output is correct
11 Correct 81 ms 10472 KB Output is correct
12 Correct 189 ms 15332 KB Output is correct
13 Correct 431 ms 55756 KB Output is correct
14 Correct 77 ms 10100 KB Output is correct
15 Correct 76 ms 10232 KB Output is correct
16 Correct 93 ms 11128 KB Output is correct
17 Correct 136 ms 19120 KB Output is correct
18 Correct 82 ms 9976 KB Output is correct
19 Correct 79 ms 10308 KB Output is correct
20 Correct 339 ms 26448 KB Output is correct
21 Correct 413 ms 56240 KB Output is correct
22 Correct 407 ms 56640 KB Output is correct
23 Correct 409 ms 56420 KB Output is correct
24 Correct 480 ms 57848 KB Output is correct
25 Correct 155 ms 19304 KB Output is correct
26 Correct 141 ms 19192 KB Output is correct
27 Correct 435 ms 56744 KB Output is correct
28 Correct 425 ms 57216 KB Output is correct
29 Correct 78 ms 10228 KB Output is correct
30 Correct 76 ms 10360 KB Output is correct
31 Correct 79 ms 10260 KB Output is correct
32 Incorrect 79 ms 10436 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 10344 KB Output is correct
2 Correct 75 ms 10224 KB Output is correct
3 Correct 79 ms 10344 KB Output is correct
4 Correct 80 ms 10220 KB Output is correct
5 Correct 94 ms 10240 KB Output is correct
6 Correct 187 ms 15608 KB Output is correct
7 Correct 394 ms 56804 KB Output is correct
8 Correct 78 ms 10212 KB Output is correct
9 Correct 79 ms 10344 KB Output is correct
10 Correct 81 ms 10344 KB Output is correct
11 Correct 81 ms 10472 KB Output is correct
12 Correct 189 ms 15332 KB Output is correct
13 Correct 431 ms 55756 KB Output is correct
14 Correct 77 ms 10100 KB Output is correct
15 Correct 76 ms 10232 KB Output is correct
16 Correct 93 ms 11128 KB Output is correct
17 Correct 136 ms 19120 KB Output is correct
18 Correct 82 ms 9976 KB Output is correct
19 Correct 79 ms 10308 KB Output is correct
20 Correct 339 ms 26448 KB Output is correct
21 Correct 413 ms 56240 KB Output is correct
22 Correct 407 ms 56640 KB Output is correct
23 Correct 409 ms 56420 KB Output is correct
24 Correct 480 ms 57848 KB Output is correct
25 Correct 155 ms 19304 KB Output is correct
26 Correct 141 ms 19192 KB Output is correct
27 Correct 435 ms 56744 KB Output is correct
28 Correct 425 ms 57216 KB Output is correct
29 Correct 78 ms 10228 KB Output is correct
30 Correct 76 ms 10360 KB Output is correct
31 Correct 79 ms 10260 KB Output is correct
32 Incorrect 79 ms 10436 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -