oj.uz

Submission #128089

# Submission time Handle Problem Language Result Execution time Memory
128089 2019-07-10T12:05:07 Z zeyad49 OBELISK (NOI14_obelisk) Java 11
5 / 25
 558 ms 50400 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 dist(dx, dy);
	}
 
	static long dist(int dx, int dy) {
		
		long ans = dy / K * 2;
		ans += dx / K * 2;
		ans += dx % K;
		ans += dy % K;

		if (dx % K > 0) {
			if (dy /K== 0)
				ans += 2;
		}
		else if (dy % K > 0 ) {
			if (dx/K== 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 93 ms 9692 KB Output is correct
2 Correct 92 ms 9624 KB Output is correct
3 Correct 94 ms 9808 KB Output is correct
4 Correct 93 ms 9724 KB Output is correct
5 Correct 102 ms 9436 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 7.0

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