Submission #930251

#TimeUsernameProblemLanguageResultExecution timeMemory
930251AiperiiiType Printer (IOI08_printer)C++14
100 / 100
135 ms95684 KiB
#include <bits/stdc++.h> #define int long long #define ff first #define ss second #define all(x) x.begin(),x.end() #define pb push_back using namespace std; const int N=1e6; struct Trie{ int out=0,last=0; map <char,int> mp; }; Trie t[N]; int cnt=0; void insert(string s){ int p=0; for(int i=0;i<s.size();i++){ if(t[p].mp[s[i]]==0){ cnt++; t[p].mp[s[i]]=cnt; } p=t[p].mp[s[i]]; } t[p].out=1; } void mark_last(string s){ int p=0; for(int i=0;i<s.size();i++){ p=t[p].mp[s[i]]; t[p].last=1; } } vector <char> ans; void get(int p,char c){ if(p!=0)ans.pb(c); if(t[p].out==1)ans.pb('P'); for(auto i : t[p].mp){ if(!t[i.ss].last)get(i.ss,i.ff); } for(auto i : t[p].mp){ if(t[i.ss].last)get(i.ss,i.ff); } ans.pb('-'); } signed main(){ ios_base::sync_with_stdio(); cin.tie(0);cout.tie(0); int n; cin>>n; vector <string> s(n); for(int i=0;i<n;i++){ cin>>s[i]; } string ls=""; for(int i=0;i<s.size();i++){ insert(s[i]); if(s[i].size()>ls.size()){ ls=s[i]; } } mark_last(ls); get(0,'S'); while(ans.back()=='-')ans.pop_back(); cout<<ans.size()<<"\n"; for(auto x : ans){ cout<<x<<"\n"; } } /* */

Compilation message (stderr)

printer.cpp: In function 'void insert(std::string)':
printer.cpp:17:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
printer.cpp: In function 'void mark_last(std::string)':
printer.cpp:28:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:56:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...