Submission #1139549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139549		rs1027	Training (IOI07_training)	Java	100 / 100	170 ms	19016 KiB

training

import java.io.*;
import java.util.*;

class Edge {
    int u, v, cost, LCA;

    public Edge(int u, int v, int cost) {
        this.u = u;
        this.v = v;
        this.cost = cost;
        this.LCA = -1;
    }
}

public class training {
    static final int MAXN = 1000;
    static final int MAXK = 10;

    static int n, m;
    static int costSum;
    static int traversalTime;
    static int[] discover = new int[MAXN];
    static int[] finish = new int[MAXN];
    static int[] depth = new int[MAXN];
    static int[] degree = new int[MAXN];
    static int[] color = new int[MAXN];
    static Pair[] parent = new Pair[MAXN];
    static List<Integer>[] treeLinks = new ArrayList[MAXN];
    static int[][] DP = new int[MAXN][1 << MAXK];
    static Edge[] E;

    static class Pair {
        int first, second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    public static void load(BufferedReader br) throws IOException {
        costSum = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        E = new Edge[m];
        for (int i = 0; i < n; i++) {
            treeLinks[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()) - 1;
            int v = Integer.parseInt(st.nextToken()) - 1;
            int cost = Integer.parseInt(st.nextToken());

            E[i] = new Edge(u, v, cost);
            costSum += cost;
            if (cost == 0) {
                treeLinks[u].add(v);
                treeLinks[v].add(u);
            }
        }
    }

    public static void treeInit(int a) {
        discover[a] = ++traversalTime;
        for (int neighbor : treeLinks[a]) {
            if (neighbor == parent[a].first) continue;

            color[neighbor] = color[a] ^ 1;
            depth[neighbor] = depth[a] + 1;
            parent[neighbor] = new Pair(a, 1 << degree[a]++);

            treeInit(neighbor);
        }
        finish[a] = ++traversalTime;
    }

    public static void init() {
        for (int[] row : DP) {
            Arrays.fill(row, 0);
        }

        traversalTime = 0;
        color[0] = 0;
        depth[0] = 0;
        parent[0] = new Pair(-1, -1);
        treeInit(0);
    }

    public static void calcLCA() {
        for (Edge edge : E) {
            int u = edge.u;
            int v = edge.v;
            while (depth[u] > depth[v]) u = parent[u].first;
            while (depth[v] > depth[u]) v = parent[v].first;
            while (u != v) {
                u = parent[u].first;
                v = parent[v].first;
            }
            edge.LCA = u;
        }
    }

    public static void solve() {
        for (Edge edge : E) {
            if (edge.cost != 0 && color[edge.u] != color[edge.v]) continue;

            int L = edge.LCA;
            int sum = edge.cost;

            Pair U = new Pair(edge.u, 0);
            while (U.first != L) {
                sum += DP[U.first][U.second];
                U = parent[U.first];
            }

            Pair V = new Pair(edge.v, 0);
            while (V.first != L) {
                sum += DP[V.first][V.second];
                V = parent[V.first];
            }

            for (int mask = (1 << degree[L]) - 1; mask >= 0; --mask) {
                if ((mask & U.second) == 0 && (mask & V.second) == 0) {
                    DP[L][mask] = Math.max(DP[L][mask], sum + DP[L][mask | U.second | V.second]);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        load(br);
        init();
        calcLCA();

        Arrays.sort(E, Comparator.comparingInt(e -> finish[e.LCA]));

        solve();

        System.out.println(costSum - DP[0][0]);
    }
}

Compilation message (stderr)

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

=======

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9