제출 #1355257

#제출 시각아이디문제언어결과실행 시간메모리
1355257frogrammerLozinke (COCI17_lozinke)C++20
10 / 100
1095 ms131072 KiB
// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;

bool custom(string s, string t){
    if(s.size()==t.size()) return s<t;
    return s.size()<t.size();
}

int checkBranch(vector<vector<int>>& adj, vector<string>& names, int parent, int node, int depth){
    if(names[parent]==names[node]) depth++;
    int sdepth = depth;
    for(int v : adj[parent]){
        if(names[v].size()<names[node].size()) continue;
        int pos = 0;
        for(char c : names[v]){
            if(c==names[node][pos]){
                pos++;
                if(pos==names[node].size()){
                    depth = checkBranch(adj, names, v, node, depth+1);
                    break;
                }
            }else pos=0;
        }
    }
    if(sdepth==depth) adj[parent].push_back(node);
    return depth;
}

int main() {
    int n;
    cin>>n;
    vector<string> names(n+1);
    for(int i=0;i<n;i++) cin>>names[i];
    names[n]="zzzzzzzzzzz";
    sort(names.rbegin(),names.rend(),custom);
    int total = 0;
    names[0] = "";

    vector<vector<int>> adj(n+1);
    for(int i=1;i<=n;i++){
        // cout<<total<<endl;
        total+=checkBranch(adj, names, 0, i, 0);
    }
    
    // for(int i=0;i<=n;i++){
    //     cout<<"node: "<<i<<" "<<names[i]<<endl;
    //     for(int v : adj[i]) cout<<names[v]<<" "<<v<<"  ";
    //     cout<<endl;
    // }
    cout<<total<<endl;
    
    
    
    
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…