oj.uz

Submission #467748

# Submission time Handle Problem Language Result Execution time Memory
467748 2021-08-24T10:23:04 Z MohamedFaresNebili Type Printer (IOI08_printer) C++14
20 / 100
 70 ms 39088 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;
    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];
    }
    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)
{
    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')); solve(next->children[l], cnt); return;
    }
    if(!found) {
        ans.pb('P');
        if(cnt+1==n) return;
        
		if(next->parent!=nullptr) { ans.pb('-'); solve(next->parent, cnt+1); }
    }
    else 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')); solve(next->children[l], cnt); return;
        }
    }
    else {
		
		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;
}

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 312 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 0 ms 204 KB didn't print every word

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 440 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1868 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 6348 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 15688 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 39088 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 30524 KB didn't print every word
2 Halted 0 ms 0 KB -