Submission #1220728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220728		uranium235	Railway (BOI17_railway)	Java	100 / 100	875 ms	112656 KiB

railway

//package ojuz;

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

public class railway {
    public static Graph g;
    public static int[] counts;
    public static Map<Integer, Integer>[] maps;
    public static List<Integer> ans = new ArrayList<>();
    public static int k;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] first = reader.readLine().split(" ");
        int n = Integer.parseInt(first[0]), m = Integer.parseInt(first[1]);
        k = Integer.parseInt(first[2]);
        g = new Graph(n, 2 * n - 2);
        maps = new Map[n];
        Arrays.setAll(maps, i -> new HashMap<>(4));
        counts = new int[m];
        for (int i = 1; i < n; i++) {
            String[] edge = reader.readLine().split(" ");
            int a = Integer.parseInt(edge[0]) - 1, b = Integer.parseInt(edge[1]) - 1;
            g.add(a, b);
            g.add(b, a);
        }

        for (int i = 0; i < m; i++) {
            String[] requests = reader.readLine().split(" ");
            counts[i] = Integer.parseInt(requests[0]);
            for (int j = 0; j < counts[i]; j++) {
                int val = Integer.parseInt(requests[j + 1]) - 1;
                maps[val].merge(i, 1, Integer::sum);
            }
        }
        dfs(0, -1, -1);
        ans.sort(Comparator.naturalOrder());
        writer.write(String.valueOf(ans.size()));
        writer.newLine();
        for (int i = 0; i < ans.size(); i++) {
            writer.write(ans.get(i) + 1 + ((i == ans.size() - 1) ? "\n" : " "));
        }
        writer.flush();
    }

    public static void dfs(int v, int p, int idx) {
        for (int x = g.head[v]; x != -1; x = g.edges[x][1]) {
            int child = g.edges[x][0];
            if (child != p) {
                dfs(child, v, x / 2);
                if (maps[child].size() > maps[v].size()) {
                    Map<Integer, Integer> temp = maps[v];
                    maps[v] = maps[child];
                    maps[child] = temp;
                }
                for (Map.Entry<Integer, Integer> e : maps[child].entrySet()) {
                    if (maps[v].getOrDefault(e.getKey(), 0) + e.getValue() == counts[e.getKey()]) {
                        maps[v].remove(e.getKey());
                    } else maps[v].merge(e.getKey(), e.getValue(), Integer::sum);
                }
            }
        }
        if (maps[v].size() >= k) ans.add(idx);
    }

    static class Graph {
        public final int[][] edges;
        public final int[] head;
        public int ptr;
        public Graph(int n, int m) {
            this.edges = new int[m][2];
            this.head = new int[n];
            Arrays.fill(head, -1);
        }

        public void add(int a, int b) {
            edges[ptr][0] = b;
            edges[ptr][1] = head[a];
            head[a] = ptr++;
        }
    }
}

Compilation message (stderr)

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

=======

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25