oj.uz

Submission #520160

# Submission time Handle Problem Language Result Execution time Memory
520160 2022-01-28T15:31:21 Z AkiYuu Type Printer (IOI08_printer) C++17
100 / 100
 125 ms 55524 KB 
/*

Problems:
Author: AkiYuu

*/

#include <bits/stdc++.h>
#define task "GROUP"
#define ll long long
#define ld long double
#define pb(u) emplace_back(u)
#define ffw(i,a,b) for (ll i = a; i <= b; i++)
#define fbw(i,b,a) for (ll i = b; i >= a; i--)
#define adj(v,adj,u) for (auto v : adj[u])
#define rep(i,a) for (auto i : a)
#define reset(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define all(a) a.begin(),a.end()

using namespace std;

void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen(task".inp", "r", stdin);
//	freopen(task".out", "w", stdout);
}

const int mxn = 1e6 + 5;
typedef pair<ll, ll> ii;

int n;
int trie[25000 * 20 + 5][26], dem;
bool isend[25000 * 20 * 26];
ii longest[25000 * 20 * 26];

void add(string s){
    int node = 0;
    for (char c : s ){
        int x = c - 'a';
        if ( trie[node][x] == 0 ) trie[node][x] = ++dem;
        node = trie[node][x];
    }
    isend[node ] = true;
}

int calc(int u){

    longest[u] = ii(1,0);
    ffw(i,0,25){
        if ( trie[u][i] == 0 ) continue;
        int v = trie[u][i];
        longest[u] = max( longest[u] , ii(calc(v) + 1, v) );
    }
    return longest[u].first;
}

vector < char > path;

void dfs(int u){

    if ( isend[u] ) {
        path.pb('P');
    }

    char LG;
    ffw(i,0,25){
        if ( trie[u][i] == 0) continue;
        int v = trie[u][i];
        if ( v == longest[u].second) {
            LG = (char) ('a' + i);
            continue;
        }
        path.pb( (char) ('a' + i) );
        dfs(v);
        path.pb( '-' );
    }
    if ( longest[u].second){
        path.pb(LG);
        dfs(longest[u].second);
        path.pb('-');
    }

}

void solve(){
    cin >> n;
    ffw(i,1,n){
        string s;
        cin >> s;
        add(s);
    }
    calc(0);
    dfs(0);
    while (sz(path) && path.back() == '-' ) path.pop_back();
    cout << sz(path) << '\n';
    for (char c : path ) cout << c << '\n';
}

int main(){
	fastio();
	int t = 1;
//	cin >> t;
	while (t--)
	solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 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 332 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 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 704 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1100 KB Output is correct
2 Correct 3 ms 1356 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3404 KB Output is correct
2 Correct 15 ms 7112 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8272 KB Output is correct
2 Correct 9 ms 2120 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 20348 KB Output is correct
2 Correct 123 ms 46616 KB Output is correct
3 Correct 55 ms 24260 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 15972 KB Output is correct
2 Correct 125 ms 55524 KB Output is correct
3 Correct 64 ms 27608 KB Output is correct
4 Correct 96 ms 52416 KB Output is correct