Submission #230661

#	Time	Username	Problem	Language	Result	Execution time	Memory
230661		Giantpizzahead	ČVENK (COI15_cvenk)	Java	60 / 100	3083 ms	95940 KiB

cvenk

/*
Solution: The labyrinth is a tree! So, do your standard shortest # of steps to meet up thing on this
tree. Find the midpoint of the people, and calculate the # of steps needed to move there.
 */

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

public class cvenk {
    int N;
    Point[] people;
    Node root = new Node(0, 0);

    class Node {
        Node left, right;
        int x, y, numPeople = 0, numPeopleST = 0;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    cvenk(BufferedReader in, PrintWriter out) throws IOException {
        StringTokenizer st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        people = new Point[N];
        int x, y;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(in.readLine());
            y = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            people[i] = new Point(x, y);
        }

        // Shuffle array to avoid malicious inputs
        Random rnd = new Random();
        for (int i = 0; i < N; i++) {
            int j = rnd.nextInt(N-i) + i;
            if (i != j) {
                Point temp = people[i];
                people[i] = people[j];
                people[j] = temp;
            }
        }

        for (Point p : people) genNodes(root, p.x, p.y, 0, 0);

        // Now do generic algorithm
        dfs(root, 0);
        answer = distSum;
        findMid(root, 0);

        out.println(answer);
    }

    long answer;
    void findMid(Node n, long dist) {
        // System.out.println("n = " + n + ", numInST = " + numInST + ", dist = " + dist);
        int left = (n.left == null) ? 0 : n.left.numPeopleST;
        int right = (n.right == null) ? 0 : n.right.numPeopleST;
        if (left == right) {
            // Midpoint is here!
            // System.out.println("midpoint " + n);
            return;
        }
        if (left > N / 2) {
            // Go to left
            answer -= (2 * left - N) * calcDist(n, n.left);
            findMid(n.left, dist + calcDist(n, n.left));
        } else if (right > N / 2) {
            // Go to right
            answer -= (2 * right - N) * calcDist(n, n.right);
            findMid(n.right, dist + calcDist(n, n.right));
        } else {
            // Midpoint is here!
            // System.out.println("midpoint " + n);
            return;
        }
    }

    long distSum = 0;
    void dfs(Node n, long dist) {
        n.numPeopleST += n.numPeople;
        distSum += dist * n.numPeople;
        if (n.left != null) {
            dfs(n.left, dist + calcDist(n, n.left));
            n.numPeopleST += n.left.numPeopleST;
        }
        if (n.right != null) {
            dfs(n.right, dist + calcDist(n, n.right));
            n.numPeopleST += n.right.numPeopleST;
        }
    }

    long calcDist(Node a, Node b) {
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }

    void genNodes(Node n, int x, int y, int offsetX, int offsetY) {
        // System.out.println(n);
        if (x == 0 && y == 0) n.numPeople++;
        else if (x < y) {
            // On left side; find how far to go down
            int dist = Integer.highestOneBit(y);
            y -= dist;
            offsetY += dist;
            while (n.left != null && n.left.y < offsetY) {
                n = n.left;
            }
            if (n.left == null || n.left.y > offsetY) {
                // Make closer node
                Node temp = new Node(offsetX, offsetY);
                // numNodes++;
                temp.left = n.left;
                n.left = temp;
            }
            // Continue genning nodes
            genNodes(n.left, x, y, offsetX, offsetY);
        } else {
            // On right side
            int dist = Integer.highestOneBit(x);
            x -= dist;
            offsetX += dist;
            while (n.right != null && n.right.x < offsetX) {
                n = n.right;
            }
            if (n.right == null || n.right.x > offsetX) {
                // Make closer node
                Node temp = new Node(offsetX, offsetY);
                // numNodes++;
                temp.right = n.right;
                n.right = temp;
            }
            // Continue genning nodes
            genNodes(n.right, x, y, offsetX, offsetY);
        }
    }

    class Point {
        int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        new cvenk(in, out);
        in.close();
        out.close();
    }
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 0 / 40