# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
311278 | 2020-10-09T20:26:32 Z | KWang31 | Travelling Salesperson (CCO20_day2problem1) | Java 11 | 81 ms | 10688 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 | 78 ms | 10344 KB | Output is correct |
2 | Correct | 79 ms | 10216 KB | Output is correct |
3 | Correct | 78 ms | 10688 KB | Output is correct |
4 | Correct | 76 ms | 10360 KB | Output is correct |
5 | Correct | 75 ms | 10344 KB | Output is correct |
6 | Correct | 77 ms | 10472 KB | Output is correct |
7 | Correct | 79 ms | 10292 KB | Output is correct |
8 | Correct | 78 ms | 10108 KB | Output is correct |
9 | Incorrect | 81 ms | 10136 KB | Expected integer, but "true" found |
10 | Halted | 0 ms | 0 KB | - |