All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Mike is a network administrator in a university. One of his primary responsibilities in the job is to create an effective firewall so that the students are not able to visit the blocked sites in the network.
The network have access to exactly N sites. Some of these can be blocked. The names of the sites will be given in lowercase English letters.
The firewall will consist of several filters. A filter is a string that should be a prefix of some blocked site, and it should not be a prefix of any unblocked site. You want to minimize the sum of length of filters in the firewall so that for each of the blocked site, there should be a filter that contains the name of blocked site(filter is a prefix of blocked site).
The first line of the input contains an integer N denoting the number of sites in the network.
Then N lines follow, each of them describes the site. Each line starts from the char С. If the site is unblocked, С is equal to '+', otherwise С is equal to '-'., followed by a string denoting the name of the site.
If it is not possible to choose set of filters and satisfy all constraints, output a single line containing an integer -1.
Otherwise, in the first line print the number of filters K in the firewall. Then print K lines, in each line print the chosen filter. Please dislpay them in lexicographical order. You can prove that answer will be unique.
- 1 ≤ N ≤ 2 * 105
- The sum of lengths of names of sites does not exceed 2*105
- No two sites have same name.
- Subtask #1 (30 points) 1 ≤ N, the sum of lengths of names of sites ≤ 3 * 103
- Subtask #2 (70 points) Original constraints
Input: 4 - codeforces + codechef - youtube + google Output: 2 codef y
You can see that the filter "codef" is a prefix of the blocked site "codeforces", but not a prefix of approved sites "codechef" and "google". Similarly, filter "y" is also a prefix of blocked site "youtube", but not a prefix of the approved sites. You can also see that there exists at least one filter for both the blocked sites "codeforces" and "youtube".
|Tags||ismagilov, long-contest, may17|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.