#51098 (C++11) No.563 超高速一人かるた large

• 問題: No.563 超高速一人かるた large
• ユーザー: koyumeishi
• 提出日時: 2015-09-26 02:50:31
• 言語: C++11 (gcc 11.4.0)
• 結果: RE
• 実行時間: -
• コード長: 1,120 bytes
• コンパイル時間: 840 ms
• コンパイル使用メモリ: 63,124 KB
• 実行使用メモリ: 51,864 KB
• 最終ジャッジ日時: 2024-10-01 19:59:50
• 合計ジャッジ時間: 5,510 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	RE	-
testcase_01	RE	-
testcase_02	RE	-
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	AC	61 ms; 51,864 KB
testcase_20	RE	-

ソースコード

#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct node{
	int cnt;
	node* e[27];
	node(){
		cnt = 0;
		for(int i=0; i<27; i++){
			e[i] = nullptr;
		}
	}

	node*& operator[](char index){
		return e[index-'a'];
	}
};

class Trie_Tree{
	vector<node*> v;
	node* root;
public:
	Trie_Tree(){
		root = new node();
		v.push_back(root);
	}
	~Trie_Tree(){
		for(int i=0; i<v.size(); i++){
			delete(v[i]);
		}
	}

	void insert(string& s){
		node* ptr = root;
		for(int i=0; i < s.size(); i++){
			ptr->cnt++;
			if( (*ptr)[ s[i] ] == nullptr){
				(*ptr)[ s[i] ] = new node();
				v.push_back( (*ptr)[ s[i] ] );
			}
			ptr = (*ptr)[s[i]];
		}
		ptr->cnt++;
	}

	int find(string& s){
		node* ptr = root;
		for(int i=0; i<=s.size(); i++){
			ptr->cnt--;
			if(ptr->cnt == 0) return i;
			ptr = (*ptr)[s[i]];
		}
		return -1;
	}
};

int main(){
	int n;
	cin >> n;
	vector<string> s(n);

	Trie_Tree trie;

	for(int i=0; i<n; i++){
		cin >> s[i];
		s[i] += 'z'+1;
		trie.insert(s[i]);
	}
	for(int i=0; i<n; i++){
		int x;
		cin >> x;
		x--;
		cout << max(1,trie.find(s[x])) << endl;
	}
	return 0;
}