-
Notifications
You must be signed in to change notification settings - Fork 1
/
D.cpp
97 lines (80 loc) · 1.79 KB
/
D.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// https://csacademy.com/contest/virtual6147/task/prefix-free-subset/statistics/
#include<bits/stdc++.h>
using namespace std;
#define D(x) cout << #x << " = " << (x) << endl;
#define endl '\n'
const int inf = INT_MAX;
const int MN = 30; // size of alphabet
const int MS = 1000100; // Number of states.
struct trie {
struct node {
int c;
int a[MN];
};
node tree[MS];
int leafs;
int nodes;
int best;
void clear() {
tree[nodes].c = 0;
memset(tree[nodes].a, -1, sizeof tree[nodes].a);
nodes++;
}
void init() {
nodes = 0;
leafs = 0;
best = 0;
clear();
}
int add (const string &s, bool query = 0) {
int cur_node = 0;
bool pre = false;
bool diff = false;
best = max(best, (int)s.size());
for (int i = 0; i < s.size(); ++i) {
int id = s[i] - 'a';
if (tree[cur_node].a[id] == -1) {
diff = true;
if (query) return 0;
tree[cur_node].a[id] = nodes;
clear();
}
else if (tree[tree[cur_node].a[id]].c > 0) {
tree[tree[cur_node].a[id]].c = 0;
pre = true;
}
cur_node = tree[cur_node].a[id];
}
if (diff) leafs ++;
if (pre) leafs --;
if (!query) tree[cur_node].c++;
return leafs;
}
};
bool cmp (string &a, string &b) {
if (a.size() == b.size()) {
return a < b;
}
return a.size() < b.size();
}
int main() {
int n, k;
cin >> n >> k;
vector<string> v(n);
for (int i = 0; i < n; ++i) cin >> v[i];
sort(v.begin(), v.end(), cmp);
v.erase(unique(v.begin(), v.end()), v.end());
trie tree;
tree.init();
bool ok = false;
for (int i = 0; i < v.size(); ++i) {
int leafs = tree.add(v[i]);
if (leafs == k) {
cout << tree.best << endl;
ok = true;
break;
}
}
if (!ok) cout << -1 << endl;
return 0;
}