oj.uz

Submission #126470

# Submission time Handle Problem Language Result Execution time Memory
126470 2019-07-07T19:55:25 Z zeyad49 OBELISK (NOI14_obelisk) Java 11
5 / 25
 1000 ms 57208 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 TreeMap<pair,Long>memo;
		static class pair implements Comparable<pair>
		{
			int a,b,c;
			pair(int x,int y,int z){
				a=x;
				b=y;
				c=z;
			}
			@Override
			public int compareTo(pair o) {
				if(a!=o.a)
					return a-o.a;
				if(b!=o.b)
					return b-o.b;
				return c-o.c;
			}
		}
		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);
			pair p=new pair(floor,i,j);
			long x=memo.getOrDefault(p, -1L);
			if(x!=-1)
				return x;
			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));
					}
				}
			}
			memo.put(p,ans);
			return 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();
			memo=new TreeMap();
			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);
					
					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 92 ms 9904 KB Output is correct
2 Correct 89 ms 9856 KB Output is correct
3 Correct 90 ms 9844 KB Output is correct
4 Correct 87 ms 9876 KB Output is correct
5 Correct 92 ms 9812 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1002 ms 57208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

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