結果

問題 No.563 超高速一人かるた large
コンテスト
ユーザー koyumeishi
提出日時 2015-09-26 16:59:55
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 930 bytes
コンパイル時間 645 ms
コンパイル使用メモリ 66,620 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-01 19:59:54
合計ジャッジ時間 4,090 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other RE * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;

struct node{
	node* e[27];
	int cnt;
	node(){
		cnt = 0;
		fill(e,e+27, nullptr);
	}
};

class trie_tree{
	node* root;
public:
	trie_tree(){
		root = new node();
		root->cnt = 1;
	}

	int insert(node* ptr, string& s, int pos){
		if(pos == s.size()) return 0;
		ptr->cnt++;
		if(ptr->e[s[pos]-'a'] == nullptr){
			ptr->e[s[pos]-'a'] = new node();
		}
		return insert(ptr->e[s[pos]-'a'], s, pos+1) + (ptr->cnt>1 ? 1 : 0);
	}
	int insert(string& s){
		return insert(root, s, 0);
	}

};

int main(){
	int n;
	cin >> n;
	vector<string> s(n);
	for(int i=0; i<n; i++){
		cin >> s[i];
		s[i] += '{';
	}
	vector<int> x(n);
	for(int i=0; i<n; i++){
		cin >> x[i];
		x[i]--;
	}

	trie_tree trie;
	vector<int> ans(n);
	for(int i=n-1; i>=0; i--){
		ans[i] = trie.insert( s[x[i]] );
	}

	for(int i=0; i<n; i++){
		cout << ans[i] << endl;
	}


}
0