QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#608177#2428. Comma SprinklerLJY_ljyAC ✓343ms224960kbC++112.6kb2024-10-03 19:22:432024-10-03 19:22:44

Judging History

你现在查看的是最新测评结果

  • [2024-10-03 19:22:44]
  • 评测
  • 测评结果:AC
  • 用时:343ms
  • 内存:224960kb
  • [2024-10-03 19:22:43]
  • 提交

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], type[MAXN], Eid;
set<int> G[MAXN][2];
bool E[MAXN][2];
// 空格 0, 句号 1,逗号 2

void dfs(int k, int t) {
	//cout << k << " " << t << endl; 
	for (auto y: G[k][t]) {
		if (!E[y][1 - t]) {
			E[y][1 - t] = true;
			dfs(y, 1 - t);
		}
	}
}

int main() {
	//freopen("test.in", "r", stdin);
	//freopen("test.out", "w", stdout);
	for (int i = 1; i < MAXN; i++) exist[i] = -1; 
	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 (exist[p] == -1) {
 			type[p] = ++Eid;
 			//printf("%d %s\n", Eid, str + 1);
		}
 		if (exist[p] == -1)
		 	exist[p] = 0;
 		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) {
			//cout << "Yes! " << type[End[i]] << " " << type[End[i + 1]] << endl;
			G[type[End[i]]][0].insert(type[End[i + 1]]); // ..., -> ,... 
		}
		if (Type[i - 1] % 3 != 1 && !E[type[End[i - 1]]][1]) {
			//cout << "Yes2! " << type[End[i]] << " " << type[End[i - 1]] << endl;
			G[type[End[i]]][1].insert(type[End[i - 1]]); // ,... -> ...,
		}
	} 
	for (int i = 1; i <= Eid; i++) E[i][0] = E[i][1] = false;
	for (int i = 1; i <= cnt; i++) {
		if (exist[End[i]] % 3 == 2 && !E[type[End[i]]][0]) {
			E[type[End[i]]][0] = true;
			dfs(type[End[i]], 0);
		}
		if (exist[End[i]] / 3 == 2 && !E[type[End[i]]][1]) {
			E[type[End[i]]][1] = true;
			dfs(type[End[i]], 1);
		} 
	} 
//	for (int i = 1; i <= Eid; i++)
//		cout << E[i][0] << " " << E[i][1] << endl;
	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 && (E[type[End[i]]][0] || E[type[End[i + 1]]][1])) printf(",");
		if (Type[i] % 3 == 1) printf(".");
		printf(" ");
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}  

詳細信息

Test #1:

score: 100
Accepted
time: 15ms
memory: 101600kb

Test #2:

score: 0
Accepted
time: 19ms
memory: 101828kb

Test #3:

score: 0
Accepted
time: 16ms
memory: 101712kb

Test #4:

score: 0
Accepted
time: 15ms
memory: 101500kb

Test #5:

score: 0
Accepted
time: 15ms
memory: 102252kb

Test #6:

score: 0
Accepted
time: 68ms
memory: 109700kb

Test #7:

score: 0
Accepted
time: 74ms
memory: 137224kb

Test #8:

score: 0
Accepted
time: 67ms
memory: 138712kb

Test #9:

score: 0
Accepted
time: 16ms
memory: 106200kb

Test #10:

score: 0
Accepted
time: 11ms
memory: 104264kb

Test #11:

score: 0
Accepted
time: 11ms
memory: 104248kb

Test #12:

score: 0
Accepted
time: 12ms
memory: 106244kb

Test #13:

score: 0
Accepted
time: 26ms
memory: 106300kb

Test #14:

score: 0
Accepted
time: 8ms
memory: 104304kb

Test #15:

score: 0
Accepted
time: 16ms
memory: 106348kb

Test #16:

score: 0
Accepted
time: 186ms
memory: 123396kb

Test #17:

score: 0
Accepted
time: 343ms
memory: 138484kb

Test #18:

score: 0
Accepted
time: 258ms
memory: 138976kb

Test #19:

score: 0
Accepted
time: 15ms
memory: 106248kb

Test #20:

score: 0
Accepted
time: 202ms
memory: 149960kb

Test #21:

score: 0
Accepted
time: 129ms
memory: 170776kb

Test #22:

score: 0
Accepted
time: 107ms
memory: 174208kb

Test #23:

score: 0
Accepted
time: 59ms
memory: 220828kb

Test #24:

score: 0
Accepted
time: 168ms
memory: 144808kb

Test #25:

score: 0
Accepted
time: 135ms
memory: 146344kb

Test #26:

score: 0
Accepted
time: 117ms
memory: 138652kb

Test #27:

score: 0
Accepted
time: 69ms
memory: 122664kb

Test #28:

score: 0
Accepted
time: 139ms
memory: 144120kb

Test #29:

score: 0
Accepted
time: 52ms
memory: 223640kb

Test #30:

score: 0
Accepted
time: 11ms
memory: 106308kb

Test #31:

score: 0
Accepted
time: 31ms
memory: 191856kb

Test #32:

score: 0
Accepted
time: 47ms
memory: 224500kb

Test #33:

score: 0
Accepted
time: 15ms
memory: 106312kb

Test #34:

score: 0
Accepted
time: 12ms
memory: 106228kb

Test #35:

score: 0
Accepted
time: 14ms
memory: 106192kb

Test #36:

score: 0
Accepted
time: 12ms
memory: 104220kb

Test #37:

score: 0
Accepted
time: 20ms
memory: 104200kb

Test #38:

score: 0
Accepted
time: 11ms
memory: 106248kb

Test #39:

score: 0
Accepted
time: 20ms
memory: 106268kb

Test #40:

score: 0
Accepted
time: 16ms
memory: 104208kb

Test #41:

score: 0
Accepted
time: 26ms
memory: 108680kb

Test #42:

score: 0
Accepted
time: 19ms
memory: 106608kb

Test #43:

score: 0
Accepted
time: 19ms
memory: 106644kb

Test #44:

score: 0
Accepted
time: 20ms
memory: 106660kb

Test #45:

score: 0
Accepted
time: 24ms
memory: 108672kb

Test #46:

score: 0
Accepted
time: 20ms
memory: 106736kb

Test #47:

score: 0
Accepted
time: 85ms
memory: 119624kb

Test #48:

score: 0
Accepted
time: 79ms
memory: 119756kb

Test #49:

score: 0
Accepted
time: 76ms
memory: 119704kb

Test #50:

score: 0
Accepted
time: 50ms
memory: 115028kb

Test #51:

score: 0
Accepted
time: 49ms
memory: 111520kb

Test #52:

score: 0
Accepted
time: 48ms
memory: 113300kb

Test #53:

score: 0
Accepted
time: 187ms
memory: 133608kb

Test #54:

score: 0
Accepted
time: 216ms
memory: 134616kb

Test #55:

score: 0
Accepted
time: 190ms
memory: 134016kb

Test #56:

score: 0
Accepted
time: 150ms
memory: 126640kb

Test #57:

score: 0
Accepted
time: 135ms
memory: 126928kb

Test #58:

score: 0
Accepted
time: 146ms
memory: 129484kb

Test #59:

score: 0
Accepted
time: 8ms
memory: 106256kb

Test #60:

score: 0
Accepted
time: 48ms
memory: 224960kb

Test #61:

score: 0
Accepted
time: 44ms
memory: 106372kb

Test #62:

score: 0
Accepted
time: 19ms
memory: 104208kb