답안 #126469

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126469 2019-07-07T19:54:37 Z zeyad49 오벨리스크 (NOI14_obelisk) Java 11
컴파일 오류
0 ms 0 KB
	import java.io.*;
	import java.util.*;
	
	public class Main {
	
		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

obelisk.java:4: error: class Main is public, should be declared in a file named Main.java
	public class Main {
	       ^
Note: obelisk.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error