oj.uz

Submission #467753

# Submission time Handle Problem Language Result Execution time Memory
467753 2021-08-24T10:33:58 Z MohamedFaresNebili Type Printer (IOI08_printer) C++14
100 / 100
 179 ms 106420 KB 
#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using ld  = long double;
using db  = double;
using ii  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vii = vector<ii>;
using vpl = vector<pl>;

#define mp make_pair
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()

const int MOD = 1000*1000*1000+7;
const long double EPS = 0.000000001;
const long long INF = 1e18;

struct node{
    node* children[26]; bool visited=false; node* parent=nullptr; bool marked=false; int last=0;
    node() {
        for(int l=0;l<26;l++) children[l]=nullptr;
    }
};
node* root; int n; string len="";
vector<char>ans;
void add(string s)
{
    node* next=root;
    for(auto u:s) {
        int i=u-'a';
        if(next->children[i]==nullptr) next->children[i]=new node();
        (next->children[i])->parent=next; next=next->children[i];
    }
    next->last=1;
    if((int)s.length()>(int)len.length()) {
        next=root;
        for(auto u:len) {
            int i=u-'a';
            (next->children[i])->marked=false;
            next=next->children[i];
        }
        next=root; len=s;
        for(auto u:len) {
            int i=u-'a';
            (next->children[i])->marked=true;
            next=next->children[i];
        }
    }
}
void solve(node* r, int cnt)
{
    if(cnt==n) return;
    node* next=r; bool found=false, used=false;
    for(int l=0;l<26;l++) {
        if(next->children[l]==nullptr) continue;
        found=true;
        if(next->children[l]->visited) continue;
        used=true;
        if((next->children[l])->marked) continue;
        (next->children[l])->visited=true;
        ans.pb(char(l+'a'));
        if((next->children[l])->last==1) { ans.pb('P'); solve(next->children[l], cnt+1); }
        else solve(next->children[l], cnt);
        return;
    }
    if(used) {
        for(int l=0;l<26;l++) {
            if(next->children[l]==nullptr) continue;
            if((next->children[l])->visited) continue;
            (next->children[l])->visited=true;
            ans.pb(char(l+'a'));
            if((next->children[l])->last==1) { ans.pb('P'); solve(next->children[l], cnt+1); }
            else solve(next->children[l], cnt);
            return;
        }
    }
    if(next->parent!=nullptr) { ans.pb('-'); solve(next->parent, cnt); }
}

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    /// freopen("closing.in", "r", stdin);
	/// freopen("closing.out", "w", stdout);
	cin>>n; root=new node();
	for(int l=0;l<n;l++) {
        string s; cin>>s; add(s);
	}
	solve(root, 0);
	cout<<(int)ans.size()<<'\n';
	for(auto u:ans) cout<<u<<'\n';
    return 0;
}

Compilation message

printer.cpp: In function 'void solve(node*, int)':
printer.cpp:63:24: warning: variable 'found' set but not used [-Wunused-but-set-variable]
   63 |     node* next=r; bool found=false, used=false;
      |                        ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 1088 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1868 KB Output is correct
2 Correct 5 ms 2432 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6252 KB Output is correct
2 Correct 23 ms 13380 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15676 KB Output is correct
2 Correct 11 ms 3548 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 38896 KB Output is correct
2 Correct 144 ms 89572 KB Output is correct
3 Correct 78 ms 46064 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 30396 KB Output is correct
2 Correct 179 ms 106420 KB Output is correct
3 Correct 93 ms 52416 KB Output is correct
4 Correct 157 ms 100496 KB Output is correct