Submission #291187

#TimeUsernameProblemLanguageResultExecution timeMemory
291187AgnimandurSailing Race (CEOI12_race)Java
60 / 100
2639 ms65556 KiB
import java.io.*; import java.util.*; class race { static final long MOD = 1000000007L; static final int INF = 50000000; static final int NINF = -50000000; public static void main(String[] args) { FastScanner sc = new FastScanner(); PrintWriter pw = new PrintWriter(System.out); int N = sc.ni(); int K = sc.ni(); ArrayList<Integer>[] graph = new ArrayList[N]; ArrayList<Integer>[] transpose = new ArrayList[N]; for (int i = 0; i < N; i++) { graph[i] = new ArrayList<Integer>(); transpose[i] = new ArrayList<Integer>(); } for (int i = 0; i < N; i++) { int j = 0; while (true) { j = sc.ni()-1; if (j==-1) break; graph[i].add(j); transpose[j].add(i); } } for (int i = 0; i < N; i++) { Collections.sort(graph[i]); Collections.sort(transpose[i]); } int[][][] dp0 = new int[N][N][2]; //maximum number of stages constrained between i and j (excluded) counterclockwise given that we are currently at i if k=0 and j if k=1. for (int size = 2; size <= N; size++) { for (int i = 0; i < N; i++) { int j = (i+size)%N; for (int k: graph[i]) { if (inRangeEx(i,j,k)) { dp0[i][j][0] = Math.max(dp0[i][j][0],1+Math.max(dp0[i][k][1],dp0[k][j][0])); } } for (int k: graph[j]) { if (inRangeEx(i,j,k)) { dp0[i][j][1] = Math.max(dp0[i][j][1],1+Math.max(dp0[i][k][1],dp0[k][j][0])); } } } } //Calculate another DP which is the maximum number of non-intersecting stages that begin in i (0 to N-1) //and end in j (0 to N-1) and are constrained by the interval [i,j] (inclusive). If 0 then we go CCW, if 1 we go CW. int[][][] dpDirect = new int[N][N][2]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { Arrays.fill(dpDirect[i][j], NINF); } } for (int j = 0; j < N; j++) { Arrays.fill(dpDirect[j][j], 0); for (int idx = 1; idx < N; idx++) { int iCCW = (j-idx+N)%N; for (int k: graph[iCCW]) { if (inRangeIn(iCCW,j,k)) { dpDirect[iCCW][j][0] = Math.max(dpDirect[iCCW][j][0],1+dpDirect[k][j][0]); } } int iCW = (j+idx)%N; for (int k: graph[iCW]) { if (inRangeIn(j,iCW,k)) { dpDirect[iCW][j][1] = Math.max(dpDirect[iCW][j][1],1+dpDirect[k][j][1]); } } } } int ans0 = -1; int h0 = -1; for (int i = 0; i < N; i++) { int val = dp0[i][i][0]; if (val > ans0) { ans0 = val; h0 = i+1; } } int[][][] choice = new int[N][N][2];//point in the transpose of i that it closest to j (0 on the left, 1 on the right) for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { Arrays.fill(choice[i][j],-1); if (i==j) continue; if (transpose[i].isEmpty()) continue; int s = transpose[i].size(); if (transpose[i].get(0) > j) { choice[i][j][0] = transpose[i].get(s-1); choice[i][j][1] = transpose[i].get(0); } else { int low = 0; int high = s-1; while (low < high) { int med = (low+high+1)/2; if (transpose[i].get(med) > j) { high = med-1; } else { low = med; } } int L = transpose[i].get(low); int R = transpose[i].get((low+1)%s); if (L==j) { Arrays.fill(choice[i][j],L); } else { choice[i][j][0] = L; choice[i][j][1] = R; } } } } //System.out.println(Arrays.deepToString(choice)); int ans1 = -1; int h1 = -1; //given an intersection: final route is a->b->...->c->d->... with edges (a,b) and (c,d) intersecting for (int b = 0; b < N; b++) { for (int c = 0; c < N; c++) { if (c==b) continue; for (int d: graph[c]) { if (d==b)continue; int a; if (inRangeEx(c,d,b)) { a = choice[b][c][0]; } else { a = choice[b][c][1]; } if (a==c||a==d||a==-1)continue; if (cross(a,b,c,d)) { int val = 2; if (inRangeEx(a,b,c)) { val += dpDirect[b][c][1]; val += Math.max(dp0[d][a][0],dp0[b][d][1]); } else { val += dpDirect[b][c][0]; val += Math.max(dp0[a][d][1],dp0[d][b][0]); } if (val > ans1) { ans1 = val; h1 = a+1; } } } } } if (K==0||(ans0 > ans1)) { pw.println(ans0); pw.println(h0); } else { pw.println(ans1); pw.println(h1); } pw.close(); } public static boolean cross(int a, int b, int c, int d) { int n1 = (inRangeEx(a,b,c)?1:0)+(inRangeEx(a,b,d)?1:0); int n2 = (inRangeEx(b,a,c)?1:0)+(inRangeEx(b,a,d)?1:0); return (n1==1&&n2==1); } //is k in between (i,j) given the wraparound public static boolean inRangeEx(int i, int j, int k) { if (i < j) return (i < k && k < j); else return (i < k || k < j); } //is k in between [i,j] given the wraparound public static boolean inRangeIn(int i, int j, int k) { if (i <= j) return (i <= k && k <= j); else return (i <= k || k <= j); } static class FastScanner { BufferedReader br; StringTokenizer st; public FastScanner() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int ni() { return Integer.parseInt(next()); } long nl() { return Long.parseLong(next()); } double nd() { return Double.parseDouble(next()); } String nextLine() { String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } }

Compilation message (stderr)

Note: race.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
#Verdict Execution timeMemoryGrader output
Fetching results...