oj.uz

Submission #126453

# Submission time Handle Problem Language Result Execution time Memory
126453 2019-07-07T19:07:01 Z zeyad49 OBELISK (NOI14_obelisk) Java 11
5 / 25
 592 ms 262144 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 HashSet<Long>[]holes;
	static HashMap<Long,Integer>map;
	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) {
		long hash=hash(i,j);
		int id=map.get(hash);
		if(memo[floor][id]!=-1)
			return memo[floor][id];
		long ans=INF;
		if(floor==0) {
			ans=dist(i, j, IEND, JEND);
		}
		else {
			
			if(holes[floor].contains(hash))
				ans=dp(floor-1,i,j);
			else
			{
				for(long hole:holes[floor]) {
					int i2=(int) (hole/MAX),j2=(int) (hole%MAX);
					ans=Math.min(ans,dp(floor-1,i2,j2)+dist(i, j, i2, j2));
				}
			}
		}
		return memo[floor][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;
		map=new HashMap();
		int sx=sc.nextInt(),sy=sc.nextInt();
		map.put(hash(sx,sy),0);
		IEND=sc.nextInt();
		JEND=sc.nextInt();
		memo=new long [n][500*100+5];
		for(long []x:memo)
			Arrays.fill(x,-1);
		holes=new HashSet[n];
		for(int floor=n-1;floor>0;floor--) {
			int h=sc.nextInt();
			holes[floor]=new HashSet();
			while(h-->0) {
				int i=sc.nextInt(),j=sc.nextInt();
				long x=hash(i,j);
				if(!map.containsKey(x))
					map.put(x,map.size());
				holes[floor].add(x);
			}
		}
		out.print(dp(n-1, sx, sy));
		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 104 ms 14044 KB Output is correct
2 Correct 102 ms 14032 KB Output is correct
3 Correct 97 ms 13816 KB Output is correct
4 Correct 98 ms 14048 KB Output is correct
5 Correct 97 ms 13828 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 546 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 592 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -