Submission #318735

# Submission time Handle Problem Language Result Execution time Memory
318735 2020-11-03T03:49:40 Z KWang31 Travelling Salesperson (CCO20_day2problem1) Java 11
25 / 25
4587 ms 222480 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.
# Verdict Execution time Memory Grader output
1 Correct 86 ms 11360 KB Output is correct
2 Correct 89 ms 11520 KB Output is correct
3 Correct 90 ms 11204 KB Output is correct
4 Correct 87 ms 11512 KB Output is correct
5 Correct 97 ms 11480 KB Output is correct
6 Correct 86 ms 11600 KB Output is correct
7 Correct 95 ms 11208 KB Output is correct
8 Correct 83 ms 11424 KB Output is correct
9 Correct 86 ms 11484 KB Output is correct
10 Correct 89 ms 11316 KB Output is correct
11 Correct 83 ms 11488 KB Output is correct
12 Correct 87 ms 11556 KB Output is correct
13 Correct 87 ms 11680 KB Output is correct
14 Correct 83 ms 11296 KB Output is correct
15 Correct 88 ms 11300 KB Output is correct
16 Correct 2693 ms 210444 KB Output is correct
17 Correct 1635 ms 178060 KB Output is correct
18 Correct 90 ms 11236 KB Output is correct
19 Correct 2399 ms 198004 KB Output is correct
20 Correct 3435 ms 205032 KB Output is correct
21 Correct 103 ms 11552 KB Output is correct
22 Correct 2381 ms 202688 KB Output is correct
23 Correct 2632 ms 220156 KB Output is correct
24 Correct 133 ms 12684 KB Output is correct
25 Correct 1851 ms 189188 KB Output is correct
26 Correct 2864 ms 211944 KB Output is correct
27 Correct 458 ms 31168 KB Output is correct
28 Correct 2503 ms 206448 KB Output is correct
29 Correct 2601 ms 209824 KB Output is correct
30 Correct 2491 ms 202980 KB Output is correct
31 Correct 2762 ms 205764 KB Output is correct
32 Correct 2801 ms 198728 KB Output is correct
33 Correct 2393 ms 177312 KB Output is correct
34 Correct 2778 ms 210972 KB Output is correct
35 Correct 2607 ms 211448 KB Output is correct
36 Correct 2700 ms 206288 KB Output is correct
37 Correct 3174 ms 207468 KB Output is correct
38 Correct 1912 ms 180916 KB Output is correct
39 Correct 2329 ms 205908 KB Output is correct
40 Correct 2059 ms 191244 KB Output is correct
41 Correct 2139 ms 191776 KB Output is correct
42 Correct 2009 ms 181168 KB Output is correct
43 Correct 2630 ms 207068 KB Output is correct
44 Correct 2498 ms 206044 KB Output is correct
45 Correct 1940 ms 188284 KB Output is correct
46 Correct 1807 ms 178076 KB Output is correct
47 Correct 2848 ms 197924 KB Output is correct
48 Correct 2204 ms 183620 KB Output is correct
49 Correct 2124 ms 181828 KB Output is correct
50 Correct 2116 ms 176616 KB Output is correct
51 Correct 3019 ms 194132 KB Output is correct
52 Correct 3320 ms 221504 KB Output is correct
53 Correct 2992 ms 207328 KB Output is correct
54 Correct 2807 ms 209676 KB Output is correct
55 Correct 3792 ms 222480 KB Output is correct
56 Correct 3378 ms 222108 KB Output is correct
57 Correct 2461 ms 175076 KB Output is correct
58 Correct 3012 ms 203684 KB Output is correct
59 Correct 3138 ms 186256 KB Output is correct
60 Correct 4312 ms 209420 KB Output is correct
61 Correct 3257 ms 194988 KB Output is correct
62 Correct 2919 ms 177612 KB Output is correct
63 Correct 2869 ms 199336 KB Output is correct
64 Correct 3222 ms 203968 KB Output is correct
65 Correct 2869 ms 198772 KB Output is correct
66 Correct 2290 ms 177620 KB Output is correct
67 Correct 2556 ms 182400 KB Output is correct
68 Correct 2926 ms 200468 KB Output is correct
69 Correct 2569 ms 179168 KB Output is correct
70 Correct 2654 ms 195904 KB Output is correct
71 Correct 3056 ms 198860 KB Output is correct
72 Correct 2971 ms 196100 KB Output is correct
73 Correct 3089 ms 204728 KB Output is correct
74 Correct 3417 ms 197112 KB Output is correct
75 Correct 3447 ms 197160 KB Output is correct
76 Correct 2932 ms 193156 KB Output is correct
77 Correct 2782 ms 182924 KB Output is correct
78 Correct 2438 ms 178532 KB Output is correct
79 Correct 2742 ms 193688 KB Output is correct
80 Correct 3161 ms 202096 KB Output is correct
81 Correct 2268 ms 181892 KB Output is correct
82 Correct 3063 ms 195096 KB Output is correct
83 Correct 3120 ms 200228 KB Output is correct
84 Correct 2627 ms 199588 KB Output is correct
85 Correct 2931 ms 205576 KB Output is correct
86 Correct 4587 ms 211632 KB Output is correct
87 Correct 665 ms 30836 KB Output is correct
88 Correct 559 ms 31152 KB Output is correct
89 Correct 3474 ms 203760 KB Output is correct
90 Correct 3324 ms 217656 KB Output is correct
91 Correct 518 ms 30312 KB Output is correct
92 Correct 593 ms 30416 KB Output is correct
93 Correct 3534 ms 204556 KB Output is correct
94 Correct 2753 ms 206920 KB Output is correct
95 Correct 541 ms 30480 KB Output is correct
96 Correct 513 ms 30888 KB Output is correct
97 Correct 2480 ms 203568 KB Output is correct
98 Correct 2674 ms 197532 KB Output is correct