제출 #1254492

#제출 시각아이디문제언어결과실행 시간메모리
1254492LM1Type Printer (IOI08_printer)C++20
100 / 100
126 ms75324 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define ff first #define ss second #define pb push_back #define vi vector<int> #define fr(i,ii,iii) for(int i=ii;i<iii;i++) const int N=25003,M=26; int n; int trie[N*20][M],ct; bool f[N*20],f1[N*20],ok; char c[N*20]; vi v[N*20]; vector<char>ans; void ins(string a){ int st=0; fr(i,0,a.size()){ int &x=trie[st][a[i]-'a']; if(x==0){ x=++ct; v[st].pb(x); } st=x; if(ok)f1[st]=1; c[st]=a[i]; } f[st]=1; } void dfs(int st){ int st1=-1; for(auto i:v[st]){ if(f1[i]){ st1=i; continue; } ans.pb(c[i]); if(f[i])ans.pb('P'); dfs(i); } if(st1!=-1){ ans.pb(c[st1]); if(f[st1])ans.pb('P'); dfs(st1); } else ans.pb('-'); } bool srt(string a,string b){ return(a.size()<b.size()); } int main(){ ios_base::sync_with_stdio(NULL);cin.tie(NULL); cin>>n; string aa[n]; fr(i,0,n){ cin>>aa[i]; } sort(aa,aa+n,srt); fr(i,0,n){ ok=(i==n-1); ins(aa[i]); } dfs(0); cout<<ans.size()-1<<"\n"; fr(i,0,ans.size()-1)cout<<ans[i]<<"\n"; }
#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...