oj.uz

답안 #80272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
80272 2018-10-19T17:11:31 Z fredbr Lozinke (COCI17_lozinke) C++17
100 / 100
 153 ms 45104 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
set<int> atuais;
int idx = 0;
 
struct Node
{
	int cnt = 0, id;
	Node* b[26];
 
	Node() {
		cnt = 0, id = ++idx;
		fill(b, b+26, nullptr);
	}
};
 
Node root = Node();
 
void add(string const& s)
{
	Node* at = &root;
	for (char a : s) {
		if (!at->b[a-'a']) at->b[a-'a'] = new Node();
		at = at->b[a-'a'];
		if (atuais.count(at->id) == 0) at->cnt++;
		atuais.insert(at->id);
	}
}
 
int cnt(string const& s)
{
	Node* at = &root;
	for (char a : s) {
		if (!at->b[a-'a']) return 0;
		at = at->b[a-'a'];
	}
	return at->cnt;
}
 
string subs(string const& s, int l, int r)
{
	string ans;
	for (int i = l; i < r; i++)
		ans.push_back(s[i]);
	return ans;
}
 
const int maxn = 20202;
 
string v[maxn];
 
int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);
	
	int n;
	cin >> n;
 
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		string& s = v[i];
 
		for (int j = 0; j < int(s.size()); j++)
			add(subs(s, j, s.size()));
		atuais.clear();
	}
 
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans += cnt(v[i])-1;
	}
 
	cout << ans << "\n";
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1148 KB Output is correct
3 Correct 3 ms 1148 KB Output is correct
4 Correct 3 ms 1184 KB Output is correct
5 Correct 8 ms 2124 KB Output is correct
6 Correct 8 ms 2188 KB Output is correct
7 Correct 10 ms 4100 KB Output is correct
8 Correct 15 ms 6532 KB Output is correct
9 Correct 33 ms 6532 KB Output is correct
10 Correct 68 ms 20328 KB Output is correct
11 Correct 50 ms 20328 KB Output is correct
12 Correct 132 ms 45104 KB Output is correct
13 Correct 91 ms 45104 KB Output is correct
14 Correct 95 ms 45104 KB Output is correct
15 Correct 153 ms 45104 KB Output is correct
16 Correct 101 ms 45104 KB Output is correct
17 Correct 31 ms 45104 KB Output is correct
18 Correct 23 ms 45104 KB Output is correct
19 Correct 91 ms 45104 KB Output is correct
20 Correct 52 ms 45104 KB Output is correct