답안 #311278

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311278 2020-10-09T20:26:32 Z KWang31 Travelling Salesperson (CCO20_day2problem1) Java 11
0 / 25
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

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# 결과 실행 시간 메모리 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 -