oj.uz

Submission #531831

# Submission time Handle Problem Language Result Execution time Memory
531831 2022-03-01T15:53:36 Z Alan Type Printer (IOI08_printer) C++17
100 / 100
 95 ms 52204 KB 
#include <bits/stdc++.h>
#define I using
#define WA using namespace std;
#define on using ll = long long;
#define Test(x) int AlanIQ = -(x);
#define should ld =
#define quit long double;
#define OI int
#define forever main
#define Alan cin.tie(0);
#define fai(x) ios::ios_base::sync_with_stdio(!x);
#define Sharky return
#define orz 0;

WA on Test (109)

struct node {
	int child[26];
	bool word;
};

node trie[500005];
bool last[500005], vis[500005];
vector<char> ans;
int lastd = 0;
string lasts;

void dfs (int u) {
	vis[u] = true;
	if (trie[u].word) ans.push_back('P');
	char c;
	int okkkookokokokoknotok = -1;
	for (int i = 0; i < 26; i++) {
		int v = trie[u].child[i];
		if (vis[v] || !v) continue;
		if (last[v]) {
			c = i + 'a';
			okkkookokokokoknotok = v;
			continue;
		}
		ans.push_back(i + 'a');
		dfs(v);
		ans.push_back('-');
	}
	if (okkkookokokokoknotok != -1) {
		ans.push_back(c);
		dfs(okkkookokokokoknotok);
		ans.push_back('-');
	}
}

I should quit OI forever () {
	Alan fai (true)
	int n, id = 0;
	cin >> n;
	string a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		int sz = a[i].size();
		if (sz > lastd) {
			lastd = sz;
			lasts = a[i];
		}
	}
	for (int i = 0; i < n; i++) {
		int cur = 0;
		bool ishouldquitoi = lasts == a[i];
		for (int j = 0; j < (int) a[i].size(); j++) {
			if (!trie[cur].child[a[i][j] - 'a']) trie[cur].child[a[i][j] - 'a'] = ++id;
			cur = trie[cur].child[a[i][j] - 'a'];
			if (ishouldquitoi) last[cur] = true;
		}
		trie[cur].word = true;
	}
	dfs(0);
	for (int i = (int) ans.size() - 1; i >= 0; i--) {
		if (ans[i] == '-') ans.pop_back();
		else break;
	}
	cout << ans.size() << "\n";
	for (auto& c : ans) cout << c << "\n";

	Sharky orz
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 300 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 704 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 2 ms 1356 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3276 KB Output is correct
2 Correct 11 ms 6712 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7888 KB Output is correct
2 Correct 6 ms 2508 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 19260 KB Output is correct
2 Correct 80 ms 43576 KB Output is correct
3 Correct 43 ms 23364 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15300 KB Output is correct
2 Correct 92 ms 52204 KB Output is correct
3 Correct 55 ms 26944 KB Output is correct
4 Correct 95 ms 49508 KB Output is correct