oj.uz

Submission #127835

# Submission time Handle Problem Language Result Execution time Memory
127835 2019-07-10T06:59:42 Z zeyad49 OBELISK (NOI14_obelisk) Java 11
5 / 25
 798 ms 54324 KB 
import java.io.*;
import java.util.*;

public class obelisk {

	static long MAX = (long) 1e9 + 5;
	static int K, IEND, JEND;
	static long INF = (long) 1e18;
	static HashMap<Long, Integer>[] holes;
	static long[] memo;

	static long dist(int i1, int j1, int i2, int j2) {
		int dx = Math.abs(i1 - i2), dy = Math.abs(j1 - j2);
		if (K == 2) {
			return dx + dy;
		}
		return Math.min(dist(dx, dy), dist(dy, dx));
	}

	static long dist(int dx, int dy) {
		if (dy % K != 0)
			return INF;
		long ans = dy / K * 2;
		ans += dx / K * 2;
		if (dx % K > 0) {
			ans += dx % K;
//			if (dy == 0)
//				ans += 2;
		}
		return ans;
	}

	static long hash(int i, int j) {
		return i * MAX + j;
	}

	static long dp(int floor, int i, int j, int id) {
		if (memo[id] != -1)
			return memo[id];

		long hash = hash(i, j);
		long ans = INF;
		if (floor == 0) {
			ans = dist(i, j, IEND, JEND);
		} else {
			int tmp = holes[floor].getOrDefault(hash, -1);
			if (tmp != -1)
				ans = dp(floor - 1, i, j, tmp);
			else {
				for (long hole : holes[floor].keySet()) {
					int i2 = (int) (hole / MAX), j2 = (int) (hole % MAX);
					ans = Math.min(ans, dp(floor - 1, i2, j2, holes[floor].get(hole)) + dist(i, j, i2, j2));
				}
			}
		}
		return memo[id] = ans;
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		K = sc.nextInt() + 1;

		int sx = sc.nextInt(), sy = sc.nextInt();
		IEND = sc.nextInt();
		JEND = sc.nextInt();
		
		int id = 1;
		holes = new HashMap[n];
		for (int floor = n - 1; floor > 0; floor--) {
			int h = sc.nextInt();
			holes[floor] = new HashMap();
			while (h-- > 0) {
				int i = sc.nextInt(), j = sc.nextInt();
				long x = hash(i, j);

				holes[floor].put(x, id++);
			}
		}
		memo = new long[id];
		Arrays.fill(memo, -1);

		out.print(dp(n - 1, sx, sy, 0));
		out.close();

	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		String nextLine() throws IOException {
			return br.readLine();
		}

		int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

		boolean ready() throws IOException {
			return br.ready();
		}

	}

}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 9944 KB Output is correct
2 Correct 92 ms 9752 KB Output is correct
3 Correct 92 ms 9668 KB Output is correct
4 Correct 90 ms 9832 KB Output is correct
5 Correct 94 ms 9812 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 11020 KB Output is correct
2 Incorrect 139 ms 12992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 798 ms 52268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 743 ms 54324 KB Output isn't correct
2 Halted 0 ms 0 KB -