| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 661167 | as111 | Type Printer (IOI08_printer) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <string>
#define MAXN 25000
using namespace std;
struct Trie {
int nex[26]; // index of next trie for each letter
int prev; // parent
bool end; // end of a word
Trie() {
fill(nex, nex + 26, -1);
prev = -1;
end = false;
}
};
Trie *tries[MAXN * 20 + 5];
int N;
char letters[200]; // store letter for each ascii value
int index = 1;
int wc = 0; //word count
void traverse(int curr) {
for (int c = 0; c < 26; c++) { // loop through each letter
if (tries[curr].nex[c] != -1) {
cout << letters[c] << endl;
traverse(tries[curr].nex[c]);
if (wc == N) return;
cout << "-" << endl;
}
}
if (tries[curr].end) {
cout << "P" << endl;
wc++;
}
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
string str;
cin >> str;
int curr = 0;
for (int j = 0; j < (int)str.length(); j++) {
int c = (int)str[j] - 97;
letters[c] = str[j];
if (tries[curr].nex[c] != -1) { // prefix recorded previously
curr = tries[curr].nex[c];
}
else {
tries[curr].nex[c] = index;
tries[index].prev = curr;
curr = index;
index++;
}
cout << curr << endl;
}
tries[curr].end = true;
cout << endl;
}
int curr = 0;
traverse(curr);
}