oj.uz

Submission #198779

# Submission time Handle Problem Language Result Execution time Memory
198779 2020-01-27T15:30:02 Z arnold518 Type Printer (IOI08_printer) C++14
100 / 100
 301 ms 113388 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 25000;

int N;
string S;
vector<char> ans;

struct Node
{
	int dep, print;
	Node *chd[30];
	Node()
	{
		int i, j;
		for(i=0; i<26; i++) chd[i]=NULL;
	}

	void update(string &S)
	{
		if(S.empty()) { print=1; return; }
		char c=S.back(); S.pop_back();
		if(chd[c-'a']==NULL) chd[c-'a']=new Node();
		chd[c-'a']->update(S);
	}

	void calc()
	{
		int i, j;
		for(i=0; i<26; i++)
		{
			if(chd[i]==NULL) continue;
			chd[i]->calc();
			dep=max(dep, chd[i]->dep+1);
		}
	}

	void dfs()
	{
		int i, j;
		int cnt=0;
		vector<int> V;
		for(i=0; i<26; i++)
		{
			if(chd[i]==NULL) continue;
			V.push_back(i);
		}
 
 		if(print) ans.push_back('P');
		sort(V.begin(), V.end(), [&](const int &p, const int &q) { return chd[p]->dep<chd[q]->dep; });
		for(auto i : V)
		{
			cnt++; ans.push_back(i+'a');
			chd[i]->dfs();
			ans.push_back('-');
		}
	}
};

Node *root=new Node();

int main()
{
	int i, j;

	cin>>N;
	for(i=1; i<=N; i++)
	{
		cin>>S;
		reverse(S.begin(), S.end());
		root->update(S);
	}
	root->calc();
	root->dfs();
	while(!ans.empty() && ans.back()=='-') ans.pop_back();
	printf("%d\n", ans.size());
	for(auto it : ans) printf("%c\n", it);
}

Compilation message

printer.cpp: In constructor 'Node::Node()':
printer.cpp:20:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
printer.cpp: In member function 'void Node::calc()':
printer.cpp:34:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
printer.cpp: In member function 'void Node::dfs()':
printer.cpp:45:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
printer.cpp: In function 'int main()':
printer.cpp:81:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", ans.size());
                 ~~~~~~~~~~^
printer.cpp:69:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 5 ms 380 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 256 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 8 ms 1320 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2040 KB Output is correct
2 Correct 12 ms 2552 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6776 KB Output is correct
2 Correct 43 ms 14456 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 16760 KB Output is correct
2 Correct 25 ms 3832 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 41460 KB Output is correct
2 Correct 243 ms 95320 KB Output is correct
3 Correct 147 ms 49268 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 32368 KB Output is correct
2 Correct 301 ms 113388 KB Output is correct
3 Correct 161 ms 55792 KB Output is correct
4 Correct 265 ms 106992 KB Output is correct