답안 #291153

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291153 2020-09-04T19:22:35 Z Agnimandur Sailing Race (CEOI12_race) Java 11
0 / 100
88 ms 10804 KB
import java.io.*;
import java.util.*;

class Main {
    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];
        for (int i = 0; i < N; i++)
            graph[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);
            }
        }

        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 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 a = 0; a < N; a++) {
            for (int b: graph[a]) {
                for (int c = 0; c < N; c++) {
                    if (c==a||c==b)
                        continue;
                    for (int d: graph[c]) {
                        if (d==a||d==b)
                            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

Note: race.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# 결과 실행 시간 메모리 Grader output
1 Runtime error 81 ms 10472 KB Execution failed because the return code was nonzero
2 Runtime error 84 ms 10360 KB Execution failed because the return code was nonzero
3 Runtime error 82 ms 10356 KB Execution failed because the return code was nonzero
4 Runtime error 81 ms 10228 KB Execution failed because the return code was nonzero
5 Runtime error 81 ms 10360 KB Execution failed because the return code was nonzero
6 Runtime error 82 ms 10472 KB Execution failed because the return code was nonzero
7 Runtime error 81 ms 10472 KB Execution failed because the return code was nonzero
8 Runtime error 84 ms 10616 KB Execution failed because the return code was nonzero
9 Runtime error 84 ms 10368 KB Execution failed because the return code was nonzero
10 Runtime error 81 ms 10500 KB Execution failed because the return code was nonzero
11 Runtime error 81 ms 10232 KB Execution failed because the return code was nonzero
12 Runtime error 79 ms 10232 KB Execution failed because the return code was nonzero
13 Runtime error 86 ms 10804 KB Execution failed because the return code was nonzero
14 Runtime error 80 ms 10488 KB Execution failed because the return code was nonzero
15 Runtime error 84 ms 10136 KB Execution failed because the return code was nonzero
16 Runtime error 83 ms 10232 KB Execution failed because the return code was nonzero
17 Runtime error 85 ms 10232 KB Execution failed because the return code was nonzero
18 Runtime error 88 ms 10724 KB Execution failed because the return code was nonzero
19 Runtime error 85 ms 10360 KB Execution failed because the return code was nonzero
20 Runtime error 85 ms 10396 KB Execution failed because the return code was nonzero