oj.uz

답안 #482748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482748 2021-10-26T08:28:40 Z urosk Type Printer (IOI08_printer) C++14
100 / 100
 173 ms 100024 KB 
/**
           __
.-.__      \ .-.  ___  __
|_|  '--.-.-(   \/\;;\_\.-._______.-.
(-)___     \ \ .-\ \;;\(   \       \ \
 Y    '---._\_((Q)) \;;\\ .-\     __(_)
 I           __'-' / .--.((Q))---'    \,
 I     ___.-:    \|  |   \'-'_          \
 A  .-'      \ .-.\   \   \ \ '--.__     '\
 |  |____.----((Q))\   \__|--\_      \     '
    ( )        '-'  \_  :  \-' '--.___\
     Y                \  \  \       \(_)
     I                 \  \  \         \,
     I                  \  \  \          \
     A                   \  \  \          '\
     |                    \  \__|           '
                           \_:.  \
                             \ \  \
                              \ \  \
                               \_\_|
**/
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x) long long
#define here cerr<<"---------------------------\n"
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pi 3.14159265358979323846
using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

void setIO(string inoutname)
{
	freopen((inoutname+".in").c_str(),"r",stdin);
    	freopen((inoutname+".out").c_str(),"w",stdout);
}
#define mod 1
ll gcd(ll a, ll b)
{
   if(b==0) return a;
   if(a==0) return b;
   if(a>=b)  return gcd(a%b,b);
   return  gcd(a,b%a);
}
ll lcm(ll a,ll b){
   return (a/gcd(a,b))*b;
}
ll add(ll a,ll b){
	a+=b;
	a+=mod;
	if(a>=mod) a%=mod;
	return a;
}
ll mul(ll a,ll b){return(a*b)%mod;}
#define maxn 25005
#define maxx 2000005
ll n;
ll t[maxx][27];
ll dp[maxx];
bool kraj[maxx];
ll id = 1;
void add(string s){
    ll i  = 0;
    for(ll j = 0;j<sz(s);j++){
        ll c = s[j]-'a';
        if(t[i][c]==0){
            t[i][c] = id;
            id++;
        }
        i = t[i][c];
    }
    kraj[i] = 1;
}
bool cmp(pll x,pll y){return dp[x.fi]<dp[y.fi];}
vector<char> ans;
void dfs1(ll u){
    for(ll i = 0;i<27;i++){
        if(t[u][i]==0) continue;
        dfs1(t[u][i]);
        dp[u]=max(dp[u],dp[t[u][i]]);
    }
    dp[u]++;
}
void dfs(ll u,char c){
    if(c!='.') ans.pb(c);
    if(kraj[u]) ans.pb('P');
    vector<pll> v;
    for(ll i = 0;i<27;i++){
        if(t[u][i]==0) continue;
        v.pb({t[u][i],i});
    }
    sort(all(v),cmp);
    for(pll x : v){
        dfs(x.fi,('a'+x.sc));
    }
    if(u!=0) ans.pb('-');
}
void tc(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n;
    while(n--){
        string s; cin >> s;
        add(s);
    }
    dfs1(0);
    dfs(0,'.');
    while(ans.back()=='-') ans.popb();
    cout<<sz(ans)<<endl;
    for(char c : ans) cout<<c<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	//setIO("lol");
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}

Compilation message

printer.cpp: In function 'void setIO(std::string)':
printer.cpp:53:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  freopen((inoutname+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:54:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |      freopen((inoutname+".out").c_str(),"w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 1100 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1868 KB Output is correct
2 Correct 3 ms 2252 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 5956 KB Output is correct
2 Correct 21 ms 12620 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 14788 KB Output is correct
2 Correct 8 ms 3404 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 36636 KB Output is correct
2 Correct 164 ms 83640 KB Output is correct
3 Correct 73 ms 42944 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 28608 KB Output is correct
2 Correct 173 ms 100024 KB Output is correct
3 Correct 88 ms 49192 KB Output is correct
4 Correct 142 ms 94364 KB Output is correct