# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
692456 | 2023-02-01T13:02:35 Z | Litusiano | Type Printer (IOI08_printer) | C++14 | 243 ms | 96608 KB |
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; //#define int long long #define f first #define s second #define ii pair<int,int> #define vi vector<int> #define vvi vector<vi> #define vvii vector<vector<ii>> #define pb push_back #define vpi vector<ii> #define forcin for(int i = 0; i<n; ++i) cin>>v[i]; #define pq priority_queue<ii> #define mp make_pair #define ld long double #define vc vector<char> #define vvc vector<vc> #define vb vector<bool> #define vvb vector<vb> #define all(a) (a).begin(),(a).end() #define For(i, n, x) for (int i = x; i < n; i++) #define rsz(a,x) assign(a,x) #define endl "\n" int n; struct Node{ unordered_map<char,Node*> son; bool aca = 0; }; void add(Node* Trie, string& x, int i){ if(i == x.size()){ Trie -> aca = 1; return; } if(Trie -> son.find(x[i]) == Trie -> son.end()){ // creo el Node del Nou caracter, Trie-> son[x[i]] = new Node; } add(Trie->son[x[i]],x,i+1); } int pc = 0; string mxs = ""; // La ultima paraula es la mes llarga vc ans; void dfs1(Node* u, int d, bool MX){ //cerr<<d<<" "<<mxs.size()<<endl; //Processo mxs la ultima, per tant MX es si nomes si es el mxs if(u->aca){ pc++; ans.pb('P'); } bool f = false; for(auto x : u->son){ if(MX && x.f == mxs[d]){ f = 1; continue; } ans.pb(x.f); dfs1(x.s,d+1,0); if(pc!=n) ans.pb('-'); } if(MX && f){ ans.pb(mxs[d]); dfs1(u->son[mxs[d]],d+1,1); if(pc!=n) ans.pb('-'); } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; Node* st = new Node; For(i,n,0){ string x; cin>>x; if(x.size() > mxs.size()) mxs = x; add(st,x,0); } // Exploro la Trie dfs1(st,0,1);// 1 pq el nul forma part de mxs cout<<ans.size()<<endl; For(i,ans.size(),0) cout<<ans[i]<<endl; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 2 ms | 1108 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1748 KB | Output is correct |
2 | Correct | 6 ms | 2132 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 5588 KB | Output is correct |
2 | Correct | 30 ms | 11880 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 13900 KB | Output is correct |
2 | Correct | 15 ms | 3284 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 95 ms | 34800 KB | Output is correct |
2 | Correct | 194 ms | 81232 KB | Output is correct |
3 | Correct | 111 ms | 40776 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 77 ms | 26292 KB | Output is correct |
2 | Correct | 243 ms | 96608 KB | Output is correct |
3 | Correct | 125 ms | 46240 KB | Output is correct |
4 | Correct | 209 ms | 91096 KB | Output is correct |