結果

問題 No.563 超高速一人かるた large
コンテスト
ユーザー koyumeishi
提出日時 2015-09-26 02:50:31
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 1,120 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 840 ms
コンパイル使用メモリ 63,124 KB
実行使用メモリ 51,864 KB
最終ジャッジ日時 2024-10-01 19:59:50
合計ジャッジ時間 5,510 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other AC * 1 RE * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;
}
0