Submission #184085

#	Time	Username	Problem	Language	Result	Execution time	Memory
184085		awlintqaa	Rima (COCI17_rima)	C++14	56 / 140	587 ms	156764 KiB

rima

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 500
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1000000007;//998244353;
const ll inf=1e18*4;
const ld pai=acos(-1);
int n,MX;
string x;
struct NODE{
        int dp,yes;
        NODE *ch[29];
        NODE(){
                dp=yes=0;
                for(int i=0;i<26;i++)ch[i]=NULL;
        }
}*root=new NODE;
void add(NODE *node,int pos,int end){
        if(pos==end){
                node->yes=1;
                return ;
        }
        int id=x[pos]-'a';
        if(node->ch[id]==NULL)node->ch[id]=new NODE;
        add(node->ch[id],pos+1,end);
}
void query(NODE *node){
        int sum=0;
        for(int i=0;i<26;i++){
                if(node->ch[i]==NULL)C;
                query(node->ch[i]);
                sum+=node->ch[i]->dp;
        }
        if(node->yes)sum++,node->dp=sum;
        MX=max(MX,sum);
}
int main(){
        cin>>n;
        for(int i=0;i<n;i++){
                cin>>x;
                reverse(x.begin(),x.end());
                add(root,0,x.size());
        }
        query(root);
        cout<<MX<<endl;
}

• Subtask 1: 56 / 140