답안 #318738

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
318738 2020-11-03T04:40:51 Z KWang31 Travelling Salesperson (CCO20_day2problem1) Java 11
25 / 25
3580 ms 224368 KB
import java.io.*; import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        boolean[][] adj=new boolean[N][N];
        for (int i = 1; i < N; i++) {
            String s=br.readLine();
            for (int j = 0; j <i; j++) {
                if(s.charAt(j)=='R'){
                    adj[i][j]=true; adj[j][i]=true;
                }
            }
        }
        boolean[] c=new boolean[N];//Tracks color of first edge, red=true
        Deque<Integer> [][] dq=new Deque[N][2];//Tracks first part (same color as first edge)
        int[] rev2=new int [N];//Tracks whether dq[1] is first or dq[0] is first
        for (int i = 0; i < N; i++) {
            dq[i][0]=new ArrayDeque<>(); dq[i][1]=new ArrayDeque<>();
            dq[i][0].add(i);//Prevents empty stuff
        }
        if(adj[0][1]){
            c[0]=true; c[1]=true;
        }
        dq[0][0].addLast(1); dq[1][0].addLast(0);
        int k;
        for (int i = 2; i < N; i++) {
            /*
            if(i==5){
                for (int j = 0; j < i; j++) {
                    System.out.println(j+" "+c[j]);
                    System.out.println(dq[j][0]);
                    System.out.println(dq[j][1]);
                }
            }
          */
            for (int j = 0; j < i; j++) {//We are adding vertex i
                k=dq[j][rev2[j]].getLast();
                /*
                if(i==4 && j==0){
                     System.out.println(k+" "+adj[k][i]+" "+c[j]);
                     System.out.println(dq[j][rev2[j]]+" "+dq[j][1-rev2[j]]);
                }
                */
                if(adj[k][i]==c[j]){
                    
                    if(dq[j][1-rev2[j]].isEmpty()){
                        if(j==0){
                            //Simply construct edge in reverse
                            
                            c[i]=c[j];
                            Iterator<Integer> it=dq[j][rev2[j]].descendingIterator();
                            while(it.hasNext()){
                                dq[i][0].addLast(it.next());
                            }
                            
                        }
                        dq[j][rev2[j]].addLast(i);//Now update
                    }else{
                        if(j==0){//Construct for i
                            c[i]=c[j];
                            
                            Iterator<Integer> it=dq[j][rev2[j]].descendingIterator();
                            while(it.hasNext()){
                            
                                dq[i][0].addLast(it.next());
                            }
                        
                            it=dq[j][1-rev2[j]].descendingIterator();
                        
                            while(it.hasNext()){
                            
                                dq[i][1].addLast(it.next());
                           
                            }
                            if(!dq[j][1-rev2[j]].isEmpty() && adj[j][dq[j][1-rev2[j]].getLast()]==c[i]){
                            
                                dq[i][0].addLast(dq[i][1].removeFirst());
                            }else if(dq[j][1-rev2[j]].isEmpty() && adj[j][dq[j][rev2[j]].getLast()]!=c[i]){
                                dq[i][1].addFirst(dq[i][0].removeLast());
                            }
                        }
                        //Now update path
                        dq[j][rev2[j]].addLast(i);
                        if(adj[i][dq[j][1-rev2[j]].getFirst()]==c[j]){
                            dq[j][rev2[j]].addLast(dq[j][1-rev2[j]].removeFirst());
                        }
                    }
                    
                }else{
                    //First update path for i
                    if(j==0){
                        
                        c[i]=!c[j];
                        dq[i][0].add(k);
                        Iterator<Integer> it=dq[j][1-rev2[j]].iterator();
                        while(it.hasNext()){
                            
                            dq[i][0].addLast(it.next());
                        }
                            
                        it=dq[j][rev2[j]].iterator();
                        while(it.hasNext()){
                            int n=it.next();
                            //System.out.println(n+"!");
                            dq[i][1].addLast(n);
                        }
                        dq[i][1].removeLast();
                        
                        if(adj[j][dq[i][rev2[i]].getLast()]==c[i]){
                             dq[i][0].addLast(dq[i][1].removeFirst());
                         }
                        
                    }
                    //Now update path for j
                    if(dq[j][rev2[j]].size()==2){
                        if(adj[j][i]!=c[j]){
                            dq[j][rev2[j]].removeFirst();
                            dq[j][1-rev2[j]].addFirst(dq[j][rev2[j]].removeFirst());
                            dq[j][1-rev2[j]].addFirst(i);
                            dq[j][1-rev2[j]].addFirst(j);
                            rev2[j]=1-rev2[j];
                            c[j]=!c[j];
                        }else{
                            dq[j][1-rev2[j]].addFirst(dq[j][rev2[j]].removeLast());
                            dq[j][rev2[j]].addLast(i);
                        }
                    }else{
                        dq[j][1-rev2[j]].addFirst(dq[j][rev2[j]].removeLast());
                        if(c[j]!=adj[i][dq[j][rev2[j]].getLast()]){
                            dq[j][1-rev2[j]].addFirst(i);
                        }else{
                            dq[j][rev2[j]].addLast(i);
                        }
                    }
                }
            }
        }
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(N).append("\n");
            Iterator<Integer> it=dq[i][rev2[i]].iterator();
            while(it.hasNext()){
                sb.append(it.next()+1).append(" ");
            }
            //sb.append("\n");
            it=dq[i][1-rev2[i]].iterator();
            while(it.hasNext()){
                sb.append(it.next()+1).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
        
    }
    
}

Compilation message

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 11364 KB Output is correct
2 Correct 88 ms 11308 KB Output is correct
3 Correct 84 ms 11440 KB Output is correct
4 Correct 78 ms 11316 KB Output is correct
5 Correct 82 ms 11440 KB Output is correct
6 Correct 87 ms 11440 KB Output is correct
7 Correct 82 ms 11312 KB Output is correct
8 Correct 90 ms 11572 KB Output is correct
9 Correct 83 ms 11448 KB Output is correct
10 Correct 83 ms 11572 KB Output is correct
11 Correct 82 ms 11204 KB Output is correct
12 Correct 80 ms 11572 KB Output is correct
13 Correct 82 ms 11300 KB Output is correct
14 Correct 84 ms 11424 KB Output is correct
15 Correct 84 ms 11556 KB Output is correct
16 Correct 2338 ms 209880 KB Output is correct
17 Correct 1763 ms 184144 KB Output is correct
18 Correct 85 ms 11348 KB Output is correct
19 Correct 2169 ms 200092 KB Output is correct
20 Correct 3170 ms 199624 KB Output is correct
21 Correct 98 ms 11772 KB Output is correct
22 Correct 2419 ms 210852 KB Output is correct
23 Correct 3197 ms 219848 KB Output is correct
24 Correct 136 ms 13272 KB Output is correct
25 Correct 2581 ms 203280 KB Output is correct
26 Correct 2565 ms 211960 KB Output is correct
27 Correct 488 ms 28928 KB Output is correct
28 Correct 3109 ms 213524 KB Output is correct
29 Correct 2441 ms 208852 KB Output is correct
30 Correct 2608 ms 209008 KB Output is correct
31 Correct 1752 ms 185368 KB Output is correct
32 Correct 2225 ms 194748 KB Output is correct
33 Correct 2620 ms 210080 KB Output is correct
34 Correct 2458 ms 205892 KB Output is correct
35 Correct 2390 ms 208076 KB Output is correct
36 Correct 3081 ms 184224 KB Output is correct
37 Correct 2425 ms 192568 KB Output is correct
38 Correct 1660 ms 180660 KB Output is correct
39 Correct 2325 ms 209620 KB Output is correct
40 Correct 2796 ms 216428 KB Output is correct
41 Correct 2079 ms 179944 KB Output is correct
42 Correct 1946 ms 182580 KB Output is correct
43 Correct 2427 ms 208608 KB Output is correct
44 Correct 2514 ms 212552 KB Output is correct
45 Correct 2298 ms 195868 KB Output is correct
46 Correct 2099 ms 176036 KB Output is correct
47 Correct 3047 ms 224368 KB Output is correct
48 Correct 2198 ms 192720 KB Output is correct
49 Correct 2434 ms 205332 KB Output is correct
50 Correct 3068 ms 213560 KB Output is correct
51 Correct 2743 ms 198448 KB Output is correct
52 Correct 3580 ms 211892 KB Output is correct
53 Correct 2844 ms 217388 KB Output is correct
54 Correct 2088 ms 176460 KB Output is correct
55 Correct 3225 ms 220632 KB Output is correct
56 Correct 3353 ms 216188 KB Output is correct
57 Correct 3564 ms 207144 KB Output is correct
58 Correct 2698 ms 196268 KB Output is correct
59 Correct 2808 ms 181488 KB Output is correct
60 Correct 3268 ms 202776 KB Output is correct
61 Correct 3168 ms 203244 KB Output is correct
62 Correct 3016 ms 200568 KB Output is correct
63 Correct 2917 ms 207472 KB Output is correct
64 Correct 2944 ms 201668 KB Output is correct
65 Correct 3196 ms 199136 KB Output is correct
66 Correct 3056 ms 198448 KB Output is correct
67 Correct 3200 ms 198500 KB Output is correct
68 Correct 2903 ms 203060 KB Output is correct
69 Correct 3192 ms 198364 KB Output is correct
70 Correct 2639 ms 182496 KB Output is correct
71 Correct 3212 ms 212340 KB Output is correct
72 Correct 2924 ms 208292 KB Output is correct
73 Correct 2722 ms 212740 KB Output is correct
74 Correct 3321 ms 206876 KB Output is correct
75 Correct 3157 ms 194736 KB Output is correct
76 Correct 2602 ms 187880 KB Output is correct
77 Correct 3117 ms 186012 KB Output is correct
78 Correct 3109 ms 204840 KB Output is correct
79 Correct 2910 ms 196960 KB Output is correct
80 Correct 2934 ms 197668 KB Output is correct
81 Correct 3097 ms 191800 KB Output is correct
82 Correct 3018 ms 200628 KB Output is correct
83 Correct 2967 ms 197280 KB Output is correct
84 Correct 2921 ms 203960 KB Output is correct
85 Correct 2947 ms 201272 KB Output is correct
86 Correct 2877 ms 207960 KB Output is correct
87 Correct 769 ms 35124 KB Output is correct
88 Correct 583 ms 32192 KB Output is correct
89 Correct 3113 ms 204340 KB Output is correct
90 Correct 3161 ms 201588 KB Output is correct
91 Correct 538 ms 30708 KB Output is correct
92 Correct 586 ms 30464 KB Output is correct
93 Correct 3168 ms 206620 KB Output is correct
94 Correct 2607 ms 183168 KB Output is correct
95 Correct 617 ms 30244 KB Output is correct
96 Correct 624 ms 31836 KB Output is correct
97 Correct 2868 ms 200740 KB Output is correct
98 Correct 2714 ms 201340 KB Output is correct