제출 #265122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
265122		idk321	Sky Walking (IOI19_walk)	Java	0 / 100	4646 ms	227108 KiB

walk

import java.util.*;

class walk {
    int n;
    int m;
    int count;
    ArrayList<int[]>[] adj;

	public long min_distance(int[] x, int[] h, int[] l, int[] r, int[] y, int s, int g) {
		n = x.length;
		m = l.length;
        TreeSet<Building> buildings = new TreeSet<Building>();
        for (int i = 0; i < n; i++) {
            Building building = new Building(i, x[i], h[i]);
            buildings.add(building);
        }
        count = n;

        adj = new ArrayList[2000000];
        for (int i = 0; i < adj.length; i++) adj[i] = new ArrayList<int[]>();

        int[][] buildingHeights = new int[n][2];
        int[][] walkHeights = new int[m][2];
        for (int i = 0; i < n; i++) {
            buildingHeights[i][0] = i;
            buildingHeights[i][1] = h[i];
        }
        for (int i = 0; i < m; i++) {
            walkHeights[i][0] = i;
            walkHeights[i][1] = y[i];
        }
        Arrays.sort(buildingHeights, new ArrayComparator());
        Arrays.sort(walkHeights, new ArrayComparator());
        int currentWalk = 0;
        int currentBuilding = 0;
        int[][] coords = new int[adj.length][2];
        while (currentWalk < m) {
            while (buildingHeights[currentBuilding][1] < walkHeights[currentWalk][1]) {
                int index = buildingHeights[currentBuilding][0];
                buildings.remove(new Building(index, x[index], h[index]));
                currentBuilding++;
            }
            int walkIndex = walkHeights[currentWalk][0];
            Set<Building> tailSet = buildings.tailSet(new Building(-1, x[l[walkIndex]], y[walkIndex]), true);
            int prevX = -1;
            for (Building b : tailSet) {
                int[] coord = {b.x, walkHeights[currentWalk][1]};
                coords[count] = coord;
                if (b.x > x[r[walkIndex]]) break;
                for (int[] adjacent : adj[b.index]) {
                    int dist2 = adjacent[1];
                    int[] ar1 = {adjacent[0], Math.abs(dist2 - y[walkIndex])};
                    int[] ar2 = {count, Math.abs(dist2 - y[walkIndex])};
                    adj[count].add(ar1);
                    adj[adjacent[0]].add(ar2);
                }
                int[] ar1 = {b.index, y[walkIndex]};
                int[] ar2 = {count, y[walkIndex]};
                adj[count].add(ar1);
                adj[b.index].add(ar2);

                if (b.x != x[l[walkIndex]]) {
                    int dist = x[b.index] - prevX;
                    int[] ar3 = {count, dist};
                    int[] ar4 = {count - 1, dist};
                    adj[count - 1].add(ar3);
                    adj[count].add(ar4);
                }
                count++;
                prevX = b.x;
            }

            currentWalk++;
        }

        long[] shortestDistance = new long[adj.length];
        Arrays.fill(shortestDistance, Long.MAX_VALUE);
        PriorityQueue<long[]> pq = new PriorityQueue<long[]>(new ArrayComparator2());
        long[] ar1 = {s, 0};
        pq.add(ar1);
        while (!pq.isEmpty()) {
            long[] node = pq.remove();
            int index = (int) node[0];
            //System.out.println(node[0] + " " + adj[index].size());
            if (node[1] >= shortestDistance[index]) continue;
            shortestDistance[index] = node[1];

            for (int[] adjacent : adj[index]) {
                if (shortestDistance[adjacent[0]] == Long.MAX_VALUE) {
                    long[] ar = {adjacent[0], adjacent[1] + shortestDistance[index]};
                    pq.add(ar);
                }
            }
        }

        return shortestDistance[g];
	}

	private static class ArrayComparator implements Comparator<int[]> {
        @Override
        public int compare(int[] o1, int[] o2) {
            return Integer.compare(o1[1], o2[1]);
        }
    }

    private static class ArrayComparator2 implements Comparator<long[]> {
        @Override
        public int compare(long[] o1, long[] o2) {
            return Long.compare(o1[1], o2[1]);
        }
    }

	private static class Building implements Comparable<Building> {
	    int index;
	    int x;
	    int h;

        public Building(int index, int x, int h) {
            this.index = index;
            this.x = x;
            this.h = h;
        }

        @Override
        public int compareTo(Building o) {
            int compare1 = Integer.compare(x, o.x);
            if (compare1 != 0) return compare1;
            return Integer.compare(h, o.h);
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43