Submission #1218303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218303		uranium235	Regions (IOI09_regions)	Java	60 / 100	3690 ms	196608 KiB

regions

//package ojuz;

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

public class regions {
    public static Graph g;
    public static int[] homes, ptrIn, ptrOut;
    public static Map<Integer, Integer> big = new HashMap<>();
    public static int timer;
    public static int[][] cache, in, out;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] first = reader.readLine().split(" ");
        int n = Integer.parseInt(first[0]), r = Integer.parseInt(first[1]), q = Integer.parseInt(first[2]);
        int[] freq = new int[r];
        homes = new int[n];
        homes[0] = Integer.parseInt(reader.readLine()) - 1;
        freq[homes[0]]++;
        g = new Graph(n, n - 1);
        for (int i = 1; i < n; i++) {
            String[] person = reader.readLine().split(" ");
            int s = Integer.parseInt(person[0]) - 1, h = Integer.parseInt(person[1]) - 1;
            homes[i] = h;
            freq[h]++;
            g.add(s, i);
        }
        int sqrt = (int) Math.sqrt(n);
        in = new int[r][];
        out = new int[r][];
        int pointer = 0;
        for (int i = 0; i < r; i++) {
            if (freq[i] >= sqrt) big.put(i, pointer++);
            in[i] = new int[freq[i]];
            out[i] = new int[freq[i]];
        }
        cache = new int[big.size()][big.size()];
        ptrIn = new int[r];
        ptrOut = new int[r];
        dfs(0, -1);
        for (int i = 0; i < q; i++) {
            String[] query = reader.readLine().split(" ");
            int r1 = Integer.parseInt(query[0]) - 1, r2 = Integer.parseInt(query[1]) - 1;
            if (!big.containsKey(r1)) {
                int ans = 0;
                for (int j = 0; j < in[r1].length; j++) {
                    // first element greater than in[r1][j]
                    int left = Arrays.binarySearch(in[r2], in[r1][j]);
                    if (left < 0) left = -left - 1;
                    else left++;
                    // first element geq in[r1][j]
                    int right = Arrays.binarySearch(in[r2], out[r1][j]);
                    if (right < 0) right = -right - 1;
                    ans += right - left;
                }
                System.out.println(ans);
            } else if (!big.containsKey(r2)) {
                int ans = 0;
                for (int j = 0; j < in[r2].length; j++) {
                    // amount of elements in in[r1] that are <= in[r2][j]
                    int left = Arrays.binarySearch(in[r1], in[r2][j]);
                    if (left < 0) left = -left - 1;
                    else left++;
                    // amount of elements in out[r1] that are <= in[r2][j]
                    int right = Arrays.binarySearch(out[r1], in[r2][j]);
                    if (right < 0) right = -right - 1;
                    else right++;
                    ans += left - right;
                }
                System.out.println(ans);
            } else {
                System.out.println(cache[big.get(r1)][big.get(r2)]);
            }
        }
    }

    public static void dfs(int v, int p) {
        int t = timer;
        in[homes[v]][ptrIn[homes[v]]++] = timer++;
        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);
            }
        }
        // everything processed so far will have out < out_v, so just search for in
        if (big.containsKey(homes[v])) {
            for (Map.Entry<Integer, Integer> e : big.entrySet()) {
                int i = e.getKey();
                int result = Arrays.binarySearch(in[i], 0, ptrIn[i], t);
                if (result < 0) result = -result - 1;
                else result++;
                cache[big.get(homes[v])][e.getValue()] += ptrIn[i] - result;
            }
        }
        out[homes[v]][ptrOut[homes[v]]++] = timer++;
    }


    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++;
        }
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 85