oj.uz

Submission #126454

# Submission time Handle Problem Language Result Execution time Memory
126454 2019-07-07T19:08:26 Z zeyad49 OBELISK (NOI14_obelisk) Java 11
5 / 25
 610 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);
				}
			}
			long ans=dp(n-1, sx, sy);
			out.print(ans>=INF?-1:ans);
			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 99 ms 13796 KB Output is correct
2 Correct 98 ms 13732 KB Output is correct
3 Correct 98 ms 13732 KB Output is correct
4 Correct 98 ms 13860 KB Output is correct
5 Correct 108 ms 13848 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 15812 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 610 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 528 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -