oj.uz

Submission #63222

# Submission time Handle Problem Language Result Execution time Memory
63222 2018-08-01T06:26:14 Z nvmdava Type Printer (IOI08_printer) C++17
100 / 100
 390 ms 86308 KB 
#include<bits/stdc++.h>
using namespace std;

struct Node{
	char val;
	int in[26];
	vector<Node*> let;
	int lon, size;
	bool word;
	
	Node(){
		memset(in, 0, sizeof(in));
		lon = 0;
		size = 2;
		word = 0;
	}
	
	bool operator<(const Node *rhs) const{
		lon < (rhs -> lon);
	}
	
} *root;


bool cmp( Node *a, Node *b ){
	return a -> lon < b -> lon;
}

void sorter(Node *now){
	
	if( now -> let.size() == 0){
		return;
	}
	for(auto x : now -> let){
		sorter( x );
		now -> size += x -> size;
	}
	
	sort(now -> let.begin(), now -> let.end(), cmp);
	now -> lon = (now -> let.back() -> lon) + 1;
}

void insert(string s, Node* now, int i, int len){
	if(i == len){
		now -> word = 1;
		return;
	}
	if(now -> in[s[i] - 'a'] == 0){
		now -> let.push_back(new Node());
		now -> in[s[i] - 'a'] = now -> let.size();
	}
	now = now -> let[now -> in[s[i] - 'a'] - 1];
	now -> val = s[i];
	insert(s, now, i + 1, len);
}

int n;
void print(Node* now){
	
	if(now != root)cout<<now -> val<<'\n';
	if(now -> let.size() == 0){
		cout<<"P\n";
		n--;
		if(n == 0){
			exit(0);
		}
	} else {
		if(now -> word == 1){
			cout<<"P\n";
			n--;
			if(n == 0){
				exit(0);
			}
		}
		for(auto x : now -> let){
			print(x);
		}
	}
	cout<<"-\n";
}

int main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int i;
	
	root = new Node();
	
	cin>>n;
	string s;
	for(i = 1; i <= n; i++){
		cin>>s;
		insert(s, root, 0, s.size());
	}
	sorter( root );
	int ans = root -> size + n - root -> lon - 2;
	cout<<ans<<"\n";
	print(root);
}

Compilation message

printer.cpp: In member function 'bool Node::operator<(const Node*) const':
printer.cpp:19:7: warning: statement has no effect [-Wunused-value]
   lon < (rhs -> lon);
   ~~~~^~~~~~~~~~~~~~
printer.cpp:20:2: warning: no return statement in function returning non-void [-Wreturn-type]
  }
  ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 496 KB Output is correct
2 Correct 4 ms 552 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 552 KB Output is correct
2 Correct 3 ms 604 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 608 KB Output is correct
2 Correct 2 ms 612 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 616 KB Output is correct
2 Correct 4 ms 1400 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2112 KB Output is correct
2 Correct 6 ms 2340 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5568 KB Output is correct
2 Correct 53 ms 11108 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 12988 KB Output is correct
2 Correct 30 ms 12988 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 31620 KB Output is correct
2 Correct 356 ms 71940 KB Output is correct
3 Correct 165 ms 71940 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 71940 KB Output is correct
2 Correct 390 ms 86308 KB Output is correct
3 Correct 195 ms 86308 KB Output is correct
4 Correct 207 ms 86308 KB Output is correct