oj.uz

Submission #498476

# Submission time Handle Problem Language Result Execution time Memory
498476 2021-12-25T09:37:47 Z Hi_Im_Not_Meo_Meo Type Printer (IOI08_printer) C++14
10 / 100
 47 ms 44216 KB 
#include"bits/stdc++.h"
#define f(i,j,k) for(int i=j;i<=k;i++)
#define pb push_back

const int N = 3e4;
using namespace std;
int n;
bool cx[N];
string s[N];
vector<int> f[N], ans;

struct Node{
	int vt;
	Node* child[30];
	Node(){ 
		vt = 0;
		f(i,0,29) child[i] = nullptr; 
	}
};

struct Trie{
	Node *root;
	Trie(){ root = new Node;}
	void __up(int i){
		int trc = 0, vvt = -1;
		Node *it = root;
		for(auto ii : s[i]){
			int j = (int) ii - 'a';
			if(!it->child[j]) it->child[j] = new Node;
			else trc = it->child[j]->vt;
			it = it->child[j];
			it->vt = i;
		}
		f[trc].pb(i);
	}
}lxv;

void dfs(int u,int pre){
	ans.pb(u);
	for(auto v: f[u]) dfs(v,u);
}

main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(cx,true,sizeof(cx));
	cin>>n;
	f(i,1,n) cin>>s[i];
	sort(s+1,s+1+n);
	//f(i,1,n) cout<<s[i]<<endl;
	f(i,1,n) lxv.__up(i);
	f(i,0,n) sort(f[i].begin(),f[i].end(),[](int u,int v){
		return s[u].size() < s[v].size();
	});
	dfs(0,-1);
	vector<char> kq;
	f(i,0,s[ans[1]].size()-1) kq.pb(s[ans[1]][i]);
	kq.pb('P');
	f(i,2,n){
		bool ok = true;
		int u = ans[i-1], v = ans[i], vt = -1;
		f(i,0,s[u].size()-1)
			if(!ok) kq.pb('-');
			else if(s[u][i] != s[v][i]){ kq.pb('-'), ok = false;}
			else vt = i;
		f(i,vt+1,s[v].size()-1) kq.pb(s[v][i]);
		kq.pb('P');
	}
	cout<<kq.size()<<'\n';
	for(auto v: kq) cout<<v<<'\n';
}

Compilation message

printer.cpp: In member function 'void Trie::__up(int)':
printer.cpp:25:16: warning: unused variable 'vvt' [-Wunused-variable]
   25 |   int trc = 0, vvt = -1;
      |                ^~~
printer.cpp: At global scope:
printer.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main(){
      | ^~~~
printer.cpp: In function 'int main()':
printer.cpp:2:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define f(i,j,k) for(int i=j;i<=k;i++)
......
   56 |  f(i,0,s[ans[1]].size()-1) kq.pb(s[ans[1]][i]);
      |    ~~~~~~~~~~~~~~~~~~~~~~      
printer.cpp:56:2: note: in expansion of macro 'f'
   56 |  f(i,0,s[ans[1]].size()-1) kq.pb(s[ans[1]][i]);
      |  ^
printer.cpp:2:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define f(i,j,k) for(int i=j;i<=k;i++)
......
   61 |   f(i,0,s[u].size()-1)
      |     ~~~~~~~~~~~~~~~~~          
printer.cpp:61:3: note: in expansion of macro 'f'
   61 |   f(i,0,s[u].size()-1)
      |   ^
printer.cpp:2:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define f(i,j,k) for(int i=j;i<=k;i++)
......
   65 |   f(i,vt+1,s[v].size()-1) kq.pb(s[v][i]);
      |     ~~~~~~~~~~~~~~~~~~~~       
printer.cpp:65:3: note: in expansion of macro 'f'
   65 |   f(i,vt+1,s[v].size()-1) kq.pb(s[v][i]);
      |   ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1972 KB Output is correct
2 Correct 1 ms 1968 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1988 KB Output is correct
2 Incorrect 1 ms 1988 KB Output isn't correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 8512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 18760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 44216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 35148 KB Output isn't correct
2 Halted 0 ms 0 KB -