結果

問題 No.563 超高速一人かるた large
ユーザー koyumeishikoyumeishi
提出日時 2015-09-26 16:59:55
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 930 bytes
コンパイル時間 702 ms
コンパイル使用メモリ 66,356 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-09 19:46:22
合計ジャッジ時間 2,783 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
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 RE -
testcase_20 RE -
権限があれば一括ダウンロードができます

ソースコード

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