Submission #529746

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)

int solve(vector<string> in){
    int n = in.size();
    constexpr int C = 26;
    array<array<vector<int>, C>, C> cnt;
    vector<int> ss(n), tt(n);
    
    vector<int> perm(C); iota(perm.begin(), perm.end(), 0);
    random_shuffle(perm.begin(), perm.end());
    rep(i, n){
        string s = in[i];
        for(char &c : s) c = perm[c - 'a'] + 'a';
        cnt[s[0]-'a'][s[s.size()-1]-'a'].emplace_back(i);
        ss[i] = s[0]-'a';
        tt[i] = s[s.size()-1]-'a';
    }
    vector<int> c(C);
    rep(i, C) rep(j, C) c[i] += cnt[i][j].size();
 
    int cnt_odd = 0;
    rep(i, C) cnt_odd += c[i] % 2;
    if(cnt_odd != 1){
        cout << "NO" << endl;
        return 1;
    }
 
    rep(root_s, C){
        if(c[root_s] % 2 == 0) continue;
        rep(root_t, C) if(!cnt[root_s][root_t].empty()){
            auto g = cnt;
 
            int root = g[root_s][root_t].back();
            g[root_s][root_t].pop_back();
 
            vector<int> inner_t_cnt(C);
            rep(i, C) inner_t_cnt[i] = (c[i] - (root_s == i))/2 - (i == root_t);
            // rep(i, C) cout << inner_t_cnt[i] << " "; cout << endl;
            vector<int> par(n);
            queue<int> q; q.emplace(root);
            while(!q.empty()){
                int u = q.front(); q.pop();
                int s = tt[u];
 
                vector<int> cs(C);
                rep(i, C) cs[i] = i;
                sort(begin(cs), end(cs), [&](int a, int b){
                        return inner_t_cnt[a] > inner_t_cnt[b];});
 
                int can = 0;
                for(auto t : cs) can += g[s][t].size();
                if(can < 2) continue; // leaf
 
                int cnt_ch = 0;
                for(auto t : cs){
                    rep(_, 2) if(cnt_ch < 2 and !g[s][t].empty() and inner_t_cnt[t] >= 1){
                        --inner_t_cnt[t];
                        int v = g[s][t].back(); g[s][t].pop_back();
                        q.emplace(v);
                        par[v] = u+1;
                        ++cnt_ch;
                    }
                }
                for(auto t : cs){
                    rep(_, 2) if(cnt_ch < 2 and !g[s][t].empty()){
                        // use as leaf
                        int v = g[s][t].back(); g[s][t].pop_back();
                        q.emplace(v);
                        par[v] = u+1;
                        ++cnt_ch;
                    }
                }
            }
            int cnt_zero = 0;
            rep(i, n) cnt_zero += par[i] == 0;
            if(cnt_zero == 1){
                cout << "YES" << endl;
                rep(i, n) cout << par[i] << endl;
                return 1;
            }
        }
    }
    return 0;
}
int main(void){
    int n; cin >> n;
    vector<string> s(n);
    rep(i, n){
        cin >> s[i];
    }
    rep(i, 100) if(solve(s)) return 0;
    cout << "NO" << endl;
    return 0;
}

Submission Info

Judge Result