oj.uz

답안 #303146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
303146 2020-09-19T23:08:27 Z llaki 슈퍼트리 잇기 (IOI20_supertrees) Java 11
21 / 100
 467 ms 57408 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(0)] = 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

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 10232 KB Output is correct
2 Correct 76 ms 10340 KB Output is correct
3 Correct 80 ms 10368 KB Output is correct
4 Correct 78 ms 10360 KB Output is correct
5 Correct 76 ms 10364 KB Output is correct
6 Correct 170 ms 14328 KB Output is correct
7 Correct 396 ms 56252 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 10232 KB Output is correct
2 Correct 76 ms 10340 KB Output is correct
3 Correct 80 ms 10368 KB Output is correct
4 Correct 78 ms 10360 KB Output is correct
5 Correct 76 ms 10364 KB Output is correct
6 Correct 170 ms 14328 KB Output is correct
7 Correct 396 ms 56252 KB Output is correct
8 Correct 76 ms 10232 KB Output is correct
9 Correct 75 ms 10232 KB Output is correct
10 Correct 81 ms 9976 KB Output is correct
11 Correct 78 ms 10108 KB Output is correct
12 Correct 174 ms 15096 KB Output is correct
13 Correct 461 ms 57408 KB Output is correct
14 Correct 77 ms 10216 KB Output is correct
15 Correct 79 ms 10380 KB Output is correct
16 Correct 91 ms 10984 KB Output is correct
17 Correct 135 ms 19192 KB Output is correct
18 Correct 77 ms 10468 KB Output is correct
19 Correct 79 ms 10348 KB Output is correct
20 Correct 296 ms 26436 KB Output is correct
21 Correct 411 ms 56824 KB Output is correct
22 Correct 424 ms 57092 KB Output is correct
23 Correct 434 ms 56312 KB Output is correct
24 Correct 467 ms 56764 KB Output is correct
25 Correct 168 ms 19512 KB Output is correct
26 Correct 153 ms 19304 KB Output is correct
27 Correct 434 ms 56364 KB Output is correct
28 Correct 417 ms 56956 KB Output is correct

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 10360 KB Output is correct
2 Correct 81 ms 10228 KB Output is correct
3 Correct 78 ms 10236 KB Output is correct
4 Incorrect 78 ms 10212 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 10232 KB Output is correct
2 Incorrect 80 ms 10196 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

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 10232 KB Output is correct
2 Correct 76 ms 10340 KB Output is correct
3 Correct 80 ms 10368 KB Output is correct
4 Correct 78 ms 10360 KB Output is correct
5 Correct 76 ms 10364 KB Output is correct
6 Correct 170 ms 14328 KB Output is correct
7 Correct 396 ms 56252 KB Output is correct
8 Correct 76 ms 10232 KB Output is correct
9 Correct 75 ms 10232 KB Output is correct
10 Correct 81 ms 9976 KB Output is correct
11 Correct 78 ms 10108 KB Output is correct
12 Correct 174 ms 15096 KB Output is correct
13 Correct 461 ms 57408 KB Output is correct
14 Correct 77 ms 10216 KB Output is correct
15 Correct 79 ms 10380 KB Output is correct
16 Correct 91 ms 10984 KB Output is correct
17 Correct 135 ms 19192 KB Output is correct
18 Correct 77 ms 10468 KB Output is correct
19 Correct 79 ms 10348 KB Output is correct
20 Correct 296 ms 26436 KB Output is correct
21 Correct 411 ms 56824 KB Output is correct
22 Correct 424 ms 57092 KB Output is correct
23 Correct 434 ms 56312 KB Output is correct
24 Correct 467 ms 56764 KB Output is correct
25 Correct 168 ms 19512 KB Output is correct
26 Correct 153 ms 19304 KB Output is correct
27 Correct 434 ms 56364 KB Output is correct
28 Correct 417 ms 56956 KB Output is correct
29 Correct 87 ms 10360 KB Output is correct
30 Correct 81 ms 10228 KB Output is correct
31 Correct 78 ms 10236 KB Output is correct
32 Incorrect 78 ms 10212 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 10232 KB Output is correct
2 Correct 76 ms 10340 KB Output is correct
3 Correct 80 ms 10368 KB Output is correct
4 Correct 78 ms 10360 KB Output is correct
5 Correct 76 ms 10364 KB Output is correct
6 Correct 170 ms 14328 KB Output is correct
7 Correct 396 ms 56252 KB Output is correct
8 Correct 76 ms 10232 KB Output is correct
9 Correct 75 ms 10232 KB Output is correct
10 Correct 81 ms 9976 KB Output is correct
11 Correct 78 ms 10108 KB Output is correct
12 Correct 174 ms 15096 KB Output is correct
13 Correct 461 ms 57408 KB Output is correct
14 Correct 77 ms 10216 KB Output is correct
15 Correct 79 ms 10380 KB Output is correct
16 Correct 91 ms 10984 KB Output is correct
17 Correct 135 ms 19192 KB Output is correct
18 Correct 77 ms 10468 KB Output is correct
19 Correct 79 ms 10348 KB Output is correct
20 Correct 296 ms 26436 KB Output is correct
21 Correct 411 ms 56824 KB Output is correct
22 Correct 424 ms 57092 KB Output is correct
23 Correct 434 ms 56312 KB Output is correct
24 Correct 467 ms 56764 KB Output is correct
25 Correct 168 ms 19512 KB Output is correct
26 Correct 153 ms 19304 KB Output is correct
27 Correct 434 ms 56364 KB Output is correct
28 Correct 417 ms 56956 KB Output is correct
29 Correct 87 ms 10360 KB Output is correct
30 Correct 81 ms 10228 KB Output is correct
31 Correct 78 ms 10236 KB Output is correct
32 Incorrect 78 ms 10212 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -