Aizu Online Judge 1217 Family Tree

■ 1217 Family Tree

入力の解析が少し面倒．クエリに対する判定は，ある人の親さえ分かれば非常に簡単に出来る．
下記のコードではchildrenも記録していたけど全く必要なかった．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n, m;  
17.  HashMap<String, String> parent;  
18.  HashMap<String, LinkedList<String>> children;  
19.   
20.  void run(){  
21.   for(;;){  
22.    n=sc.nextInt();  
23.    m=sc.nextInt();  
24.    if((n|m)==0){  
25.     break;  
26.    }  
27.    parent=new HashMap<String, String>();  
28.    children=new HashMap<String, LinkedList<String>>();  
29.    sc.nextLine();  
30.    String p="", r=""; // 親, 1つ前  
31.    children.put(p, new LinkedList<String>());  
32.    int x=-1;  
33.    for(int j=0; j<n; j++){  
34.     String s=sc.nextLine();  
35.     int y=s.length()-s.replaceAll(" ", "").length();  
36.     s=s.replaceAll(" ", "");  
37.     // debug(s, r, p);  
38.     if(y>x){  
39.      p=r;  
40.     }else if(y<x){  
41.      for(int i=y; i<x; i++){  
42.       p=parent.get(p);  
43.      }  
44.     }  
45.     parent.put(s, p);  
46.     children.get(p).add(s);  
47.     children.put(s, new LinkedList<String>());  
48.     x=y;  
49.     r=s;  
50.    }  
51.    // dfs("", "");  
52.    for(int i=0; i<m; i++){  
53.     String s=sc.next();  
54.     sc.next();  
55.     sc.next();  
56.     char c=sc.next().charAt(0);  
57.     sc.next();  
58.     String t=sc.next();  
59.     t=t.substring(0, t.length()-1);  
60.     boolean f=false;  
61.     switch(c){  
62.     case 'c':  
63.      f=parent.containsKey(s)&&parent.get(s).equals(t);  
64.      break;  
65.     case 'p':  
66.      f=parent.containsKey(t)&&parent.get(t).equals(s);  
67.      break;  
68.     case 's':  
69.      f=parent.containsKey(s)&&parent.containsKey(t)  
70.        &&parent.get(s).equals(parent.get(t));  
71.      break;  
72.     case 'd':  
73.      for(s=parent.get(s); s!=null; s=parent.get(s)){  
74.       f|=s.equals(t);  
75.      }  
76.      break;  
77.     case 'a':  
78.      for(t=parent.get(t); t!=null; t=parent.get(t)){  
79.       f|=t.equals(s);  
80.      }  
81.      break;  
82.     }  
83.     println(f?"True":"False");  
84.    }  
85.    println("");  
86.   }  
87.  }  
88.   
89.  void dfs(String s, String tab){  
90.   for(String t : children.get(s)){  
91.    debug(tab, t, parent.get(t));  
92.    dfs(t, tab+"\t");  
93.   }  
94.  }  
95.   
96.  void debug(Object... os){  
97.   // System.err.println(Arrays.deepToString(os));  
98.  }  
99.   
100.  void print(String s){  
101.   System.out.print(s);  
102.  }  
103.   
104.  void println(String s){  
105.   System.out.println(s);  
106.  }  
107.   
108.  public static void main(String[] args){  
109.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
110.   new Main().run();  
111.  }  
112. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 HashMap<String, String> parent;
 HashMap<String, LinkedList<String>> children;

 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   parent=new HashMap<String, String>();
   children=new HashMap<String, LinkedList<String>>();
   sc.nextLine();
   String p="", r=""; // 親, 1つ前
   children.put(p, new LinkedList<String>());
   int x=-1;
   for(int j=0; j<n; j++){
    String s=sc.nextLine();
    int y=s.length()-s.replaceAll(" ", "").length();
    s=s.replaceAll(" ", "");
    // debug(s, r, p);
    if(y>x){
     p=r;
    }else if(y<x){
     for(int i=y; i<x; i++){
      p=parent.get(p);
     }
    }
    parent.put(s, p);
    children.get(p).add(s);
    children.put(s, new LinkedList<String>());
    x=y;
    r=s;
   }
   // dfs("", "");
   for(int i=0; i<m; i++){
    String s=sc.next();
    sc.next();
    sc.next();
    char c=sc.next().charAt(0);
    sc.next();
    String t=sc.next();
    t=t.substring(0, t.length()-1);
    boolean f=false;
    switch(c){
    case 'c':
     f=parent.containsKey(s)&&parent.get(s).equals(t);
     break;
    case 'p':
     f=parent.containsKey(t)&&parent.get(t).equals(s);
     break;
    case 's':
     f=parent.containsKey(s)&&parent.containsKey(t)
       &&parent.get(s).equals(parent.get(t));
     break;
    case 'd':
     for(s=parent.get(s); s!=null; s=parent.get(s)){
      f|=s.equals(t);
     }
     break;
    case 'a':
     for(t=parent.get(t); t!=null; t=parent.get(t)){
      f|=t.equals(s);
     }
     break;
    }
    println(f?"True":"False");
   }
   println("");
  }
 }

 void dfs(String s, String tab){
  for(String t : children.get(s)){
   debug(tab, t, parent.get(t));
   dfs(t, tab+"\t");
  }
 }

 void debug(Object... os){
  // System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}