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