#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef pair<int,int> pii;
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
#define REPb(j, d, c) for (int j = int(d); j >= int(c); j--)
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
vector<char> all_actions;
int trie[int(6e5)][26];
bool is_end[int(6e5)];
bool is_long[int(6e5)];
bool comper(string a, string b)
{
if(a.size() < b.size()) return true;
if(a.size() > b.size()) return false;
REP(i,0,a.size()-1)
{
if((int)a[i] > (int)b[i])
{
return false;
}
if((int)a[i] < (int)b[i])
{
return true;
}
}
return true;
}
void dfs(int v)
{
if(is_end[v]) all_actions.pb('P'); // cout << "P" << endl;
pii loong = {-1,-1};
REP(i,0,25)
{
if(trie[v][i]!=0)
{
if(is_long[trie[v][i]])
{
loong = {v,i};
continue;
}
all_actions.pb((char)(i+97)); // cout << (char)(i+97) << endl;
dfs(trie[v][i]);
}
}
if(loong.ff != -1)
{
all_actions.pb((char)(loong.ss+97)); // cout << (char)(loong.ss+97) << endl;
dfs(trie[loong.ff][loong.ss]);
}
all_actions.pb({'-'}); // cout << "-" << endl;
}
int main() // LL OR INT?? DELETED IFSTREAM??
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//ifstream cin("input.txt");
//ifstream cin("test.in");
//ofstream cout("test.out");
int n;
cin>>n;
vector<string> words;
REP(i,1,n)
{
string w;
cin>>w;
words.pb(w);
}
sort(words.begin(),words.end(),comper);
// build the trie
int nex=1;
REP(wi,0,n-1)
{
string w = words[wi];
int len = w.size();
int cur=0;
REP(i,0,len-1)
{
if(trie[cur][(int)w[i]-97]!=0)
{
cur=trie[cur][(int)w[i]-97];
}
else
{
trie[cur][(int)w[i]-97]=nex;
cur=nex;
nex++;
}
if(i==len-1)
{
is_end[cur]=true;
}
if(wi==n-1)
{
is_long[cur] = true;
}
}
}
// Euler tour the trie
dfs(0);
int ans = all_actions.size()-1;
while(all_actions[ans]=='-') ans--;
cout << ans+1 << endl;
REP(i,0,ans)
{
cout << all_actions[i] << endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1152 KB |
Output is correct |
2 |
Correct |
4 ms |
1408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
3328 KB |
Output is correct |
2 |
Correct |
22 ms |
6560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
7932 KB |
Output is correct |
2 |
Correct |
18 ms |
2464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
19216 KB |
Output is correct |
2 |
Correct |
131 ms |
42324 KB |
Output is correct |
3 |
Correct |
91 ms |
23148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
15468 KB |
Output is correct |
2 |
Correct |
161 ms |
50236 KB |
Output is correct |
3 |
Correct |
109 ms |
26228 KB |
Output is correct |
4 |
Correct |
153 ms |
47596 KB |
Output is correct |