Submission #303207

#	Time	Username	Problem	Language	Result	Execution time	Memory
303207		llaki	Connecting Supertrees (IOI20_supertrees)	Java	96 / 100	938 ms	66388 KiB

supertrees

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

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);
        }
        if (areAllAtMostTwo(p)) {
            return constructAtMostTwo(p, n);
        }
        int[][] answer = new int[n][n];

        grader.build(answer);
        return 1;
    }

    int constructAtMostTwo(int[][] p, int n) {
        int[] comp = new int[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;
            }
        }
        @SuppressWarnings({"rawtypes", "unchecked"})
        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);
        }
        int[][] b = new int[n][n];
        @SuppressWarnings({"rawtypes", "unchecked"})
        ArrayList<Integer>[] G = new ArrayList[n];
        int[] used = new int[n];
        for (int i = 0; i < n; i++) G[i] = new ArrayList<>();
        for (int i = 0; i < c; i++) {
            boolean add = addForComponent(2, C, i, p, n, used, b, G);
            if (!add) return 0;
        }
        grader.build(b);
        return 1;
    }

    boolean addForComponent(int num, ArrayList<Integer>[] C, int i, int[][] p, int n, int[] used,
                            int[][] b, ArrayList<Integer>[] G) {
        if (C[i].size() <= 1) return true;
        ArrayList<Integer> nodes = C[i];
        for (int nd : nodes) {
            for (int j = 0; j < n; j++) {
                if (p[nd][j] == 1 && j != nd) {
                    G[nd].add(j);
                }
            }
        }
        ArrayList<Integer> cycle = new ArrayList<>();
        ArrayList<ArrayList<Integer>> comps = new ArrayList<>();
        for (int nd : nodes) {
            if (used[nd] > 0) continue;
            ArrayList<Integer> ls = new ArrayList<>();
            dfsMakeTree(nd, nd, b, G, used, ls);
            comps.add(ls);
            for (int x = 0; x < ls.size(); x++) {
                for (int y = x + 1; y < ls.size(); y++) {
                    if (p[ls.get(x)][ls.get(y)] != 1 ||
                            p[ls.get(y)][ls.get(x)] != 1) return false;
                }
            }
            cycle.add(nd);
        }
        if (cycle.size() <= 1) return true;
        if (cycle.size() == 2) return false;
        for (int x = 0; x < cycle.size(); x++) {
            for (int y = 0; y < cycle.size(); y++) {
                if (x == y) continue;
                if (p[cycle.get(x)][cycle.get(y)] != num) return false;
            }
        }
        for (int x = 0; x < comps.size(); x++) {
            ArrayList<Integer> l1 = comps.get(x);
            for (int y = x + 1; y < comps.size(); y++) {
                ArrayList<Integer> l2 = comps.get(y);
                for (int w : l1) {
                    for (int v : l2) {
                        if (p[w][v] != num || p[v][w] != num) {
                            return false;
                        }
                    }
                }
            }
        }
        for (int j = 0; j < cycle.size(); j++) {
            int x = cycle.get(j), y = cycle.get((j + 1) % cycle.size());
            b[x][y] = 1;
            b[y][x] = 1;
        }
        return true;
    }

    void dfsMakeTree(int v, int p, int[][] b, ArrayList<Integer>[] G, int[] used,
                     ArrayList<Integer> ls) {
        if (v != p) {
            b[v][p] = 1;
            b[p][v] = 1;
        }
        ls.add(v);
        used[v] = 1;
        for (int to : G[v]) {
            if (to == p || used[to] > 0) continue;
            dfsMakeTree(to, v, b, G, used, ls);
        }
    }

    int constructAllZeroOrTwo(int[][] p, int n) {
        int[] comp = new int[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;
            }
        }
        @SuppressWarnings({"rawtypes", "unchecked"})
        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);
        }
        int[][] b = new int[n][n];
        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;
    }

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

    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;
            }
        }
        @SuppressWarnings({"rawtypes", "unchecked"})
        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 (j != i && 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;
    }
}

/**
10
1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2
2 2 2 2 2 1 2 2 2 2
2 2 2 2 2 2 1 1 1 1
2 2 2 2 2 2 1 1 1 1
2 2 2 2 2 2 1 1 1 1
2 2 2 2 2 2 1 1 1 1
 * */

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 0 / 4