oj.uz

Submission #303130

# Submission time Handle Problem Language Result Execution time Memory
303130 2020-09-19T22:52:39 Z llaki Connecting Supertrees (IOI20_supertrees) Java 11
11 / 100
 387 ms 56084 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);
        }
        int[][] answer = new int[n][n];

        grader.build(answer);
        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;
                }
            }
        }
        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 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 80 ms 10216 KB Output is correct
2 Correct 76 ms 10100 KB Output is correct
3 Correct 77 ms 10104 KB Output is correct
4 Correct 76 ms 10216 KB Output is correct
5 Correct 77 ms 10108 KB Output is correct
6 Correct 149 ms 14708 KB Output is correct
7 Correct 387 ms 56084 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10216 KB Output is correct
2 Correct 76 ms 10100 KB Output is correct
3 Correct 77 ms 10104 KB Output is correct
4 Correct 76 ms 10216 KB Output is correct
5 Correct 77 ms 10108 KB Output is correct
6 Correct 149 ms 14708 KB Output is correct
7 Correct 387 ms 56084 KB Output is correct
8 Incorrect 77 ms 10360 KB Answer gives possible 0 while actual possible 1
9 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 10192 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 10104 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10216 KB Output is correct
2 Correct 76 ms 10100 KB Output is correct
3 Correct 77 ms 10104 KB Output is correct
4 Correct 76 ms 10216 KB Output is correct
5 Correct 77 ms 10108 KB Output is correct
6 Correct 149 ms 14708 KB Output is correct
7 Correct 387 ms 56084 KB Output is correct
8 Incorrect 77 ms 10360 KB Answer gives possible 0 while actual possible 1
9 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10216 KB Output is correct
2 Correct 76 ms 10100 KB Output is correct
3 Correct 77 ms 10104 KB Output is correct
4 Correct 76 ms 10216 KB Output is correct
5 Correct 77 ms 10108 KB Output is correct
6 Correct 149 ms 14708 KB Output is correct
7 Correct 387 ms 56084 KB Output is correct
8 Incorrect 77 ms 10360 KB Answer gives possible 0 while actual possible 1
9 Halted 0 ms 0 KB -