QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#607897 | #2428. Comma Sprinkler | LJY_ljy | TL | 69ms | 131988kb | C++11 | 2.2kb | 2024-10-03 16:57:37 | 2024-10-03 16:57:38 |
Judging History
answer
//Trie树(字典树)练习
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int MAXN = 1000010;
char str[MAXN], Ans[MAXN];
int exist[MAXN], End[MAXN], len, Bound[MAXN];
int eid, cnt, nex[MAXN][30], Type[MAXN];
set<int> G[MAXN][2];
bool used[MAXN][2];
queue<int> q1, q2;
// 空格 0, 句号 1,逗号 2
int main() {
while (scanf("%s", str + 1) != EOF) {
int n = strlen(str + 1), m;
cnt++;
if ('a' <= str[n] && str[n] <= 'z') m = n;
else m = n - 1;
Type[cnt] = (Type[cnt - 1] % 3) * 3;
if ('.' == str[n]) Type[cnt] ++;
if (',' == str[n]) Type[cnt] += 2;
for (int i = len + 1; i <= len + m; i++)
Ans[i] = str[i - len];
len = len + m;
Bound[cnt] = len;
int p = 0;
for (int i = 1; i <= m; i++) {
int c = str[i] - 'a';
if (!nex[p][c]) nex[p][c] = ++eid;
p = nex[p][c];
}
if (Type[cnt] % 3 == 2 && exist[p] % 3 == 0)
exist[p] += 2;
if (Type[cnt] / 3 == 2 && exist[p] / 3 == 0)
exist[p] += 6;
End[cnt] = p;
}
for (int i = 1; i <= cnt; i++) {
if (Type[i + 1] / 3 != 1)
G[End[i]][0].insert(End[i + 1]); // ..., -> ,...
if (Type[i - 1] % 3 != 1)
G[End[i]][1].insert(End[i - 1]); // ,... -> ...,
}
for (int i = 1; i <= cnt; i++) {
if (exist[End[i]] % 3 == 2) {
q1.push(End[i]);
used[End[i]][0] = true;
}
if (exist[End[i]] / 3 == 2) {
q2.push(End[i]);
used[End[i]][1] = true;
}
}
while ((!q1.empty()) || (!q2.empty())) {
while (!q1.empty()) {
int x = q1.front();
for (auto y:G[x][0]) {
if (!used[y][1]) {
used[y][1] = true;
q2.push(y);
}
}
q1.pop();
}
while (!q2.empty()) {
int x = q2.front();
for (auto y:G[x][1]) {
if (!used[y][0]) {
used[y][0] = true;
q1.push(y);
}
}
q2.pop();
}
}
for (int i = 1; i <= cnt; i++) {
for (int j = Bound[i - 1] + 1; j <= Bound[i]; j++)
printf("%c", Ans[j]);
if (Type[i] % 3 != 1 && (used[End[i]][0] || used[End[i + 1]][1])) printf(",");
if (Type[i] % 3 == 1) printf(".");
printf(" ");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 11ms
memory: 102168kb
Test #2:
score: 0
Accepted
time: 12ms
memory: 99976kb
Test #3:
score: 0
Accepted
time: 12ms
memory: 102292kb
Test #4:
score: 0
Accepted
time: 17ms
memory: 102112kb
Test #5:
score: 0
Accepted
time: 11ms
memory: 100328kb
Test #6:
score: 0
Accepted
time: 68ms
memory: 114452kb
Test #7:
score: 0
Accepted
time: 59ms
memory: 130836kb
Test #8:
score: 0
Accepted
time: 69ms
memory: 131988kb
Test #9:
score: 0
Accepted
time: 11ms
memory: 102068kb
Test #10:
score: 0
Accepted
time: 15ms
memory: 102132kb
Test #11:
score: 0
Accepted
time: 11ms
memory: 102072kb
Test #12:
score: 0
Accepted
time: 12ms
memory: 102068kb
Test #13:
score: 0
Accepted
time: 11ms
memory: 100132kb
Test #14:
score: 0
Accepted
time: 11ms
memory: 102156kb
Test #15:
score: 0
Accepted
time: 15ms
memory: 102140kb
Test #16:
score: -100
Time Limit Exceeded