AOJ Problem 1217 : Family Tree

404 Not Found ← 問題文

木構造が与えられた後に、関係を表す命題が与えられるので、真か偽か判定する。

解くにあたっては、各ノードの親の情報だけあればいい。なぜなら、

1. X is a child of Y.　→　Xの親がYである。
2. X is the parent of Y.　→　Yの親がXである。
3. X is a sibling of Y. →　XとYの親が同じである。
4. X is a descendant of Y. →　Xの親を再帰的に辿っていくとYにたどり着く。
5. X is an ancestor of Y.　→　Yの親を再帰的に辿っていくとXにたどり着く。

と言い換えれるから。

特に難しいと感じたのは、問題なのは入力の部分……なんですけど問題文に書いてある

John is the parent of Robert.

Robert is a sibling of Nancy.

David is a descendant of Robert.

は全部真であるみたいな解釈してしまったせいで、真偽判定の部分でもクソ悩んでしまった。なんで"David is a descendant of Robert."が真なのみたいな。

冷静になって問題文読んでみたら3つ目は偽でっす☆とか書いてた。許せない。

てか問題文を適当にしか読まない自分が許せない。

/*
	X is a child of Y.　Xの親を調べてく。
	X is the parent of Y.　Yの親を調べてく
	X is a sibling of Y. XとYの深さが同じか確認する
	X is a descendant of Y. Xの親を再帰的に
	X is an ancestor of Y.　Yの親を再帰的に
*/
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
#include <sstream>
using namespace std;

map<string,string> data;
vector< pair<string,int> > cpy;

int n,m,I,back;

void input(string parent,int depth){
	while( I < n ){
		string nstr = cpy[I].first;
		int ndp = cpy[I].second;
		data[nstr] = parent;
		I++;
		if(depth < ndp){
			input(nstr,ndp);
			if(back){
				back--;
				return;
			}
		}else if(depth > ndp){
			back = depth-ndp-1;
			return;
		}
	}
}

bool func(string a,string b){
	if(a == "")return false;
	return a==b ? true : func(data[a],b);
}

int main(){
	string s; // 文字列入力用・汎用一時変数
	
	while(scanf("%d %d\n",&n,&m) , n){
		/* 初期化 */
		vector< pair<string,int> > in(n,make_pair("",-1));
		data.clear();
		
		/* やりやすいように、入力データの構造をいじって配列につっこむ */
		for(int i=0;i<n;i++){
			getline(cin,s);
			if(i){
				in[i-1].second = count(s.begin(),s.end(),' ');
			}
			s.erase(remove(s.begin(),s.end(),' '),s.end());
			in[i].first = s;
		}
		
		/* 入力処理 */
		cpy=in;
		I = back = 0;
		input("",0);
		
		/* 真偽判定 */
		bool flag;
		for(int i=0;i<m;i++){
			vector<string> tmp;

			getline(cin,s);
			s = s.substr(0,s.length()-1);
			stringstream ss(s);	
			while(ss >> s)tmp.push_back(s);
			string X = tmp[0], Y = tmp[5] , type = tmp[3];
		
			if(type == "child")flag = (data[X] == Y);
			if(type == "parent")flag = (data[Y] == X);
			if(type == "sibling")flag = (data[X] == data[Y]);
			if(type == "descendant")flag = (func(X,Y)) ;
			if(type == "ancestor")flag = (func(Y,X)) ;
			
			cout << (flag?"True":"False") << endl;
		}
		cout << endl;
	}
}