| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 311279 | KWang31 | Travelling Salesperson (CCO20_day2problem1) | Java | 3574 ms | 242152 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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 (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||