# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
318738 | 2020-11-03T04:40:51 Z | KWang31 | Travelling Salesperson (CCO20_day2problem1) | Java 11 | 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
# | Verdict | Execution time | Memory | 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 |