Submission #1520989

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;

#define OUT(x)  cerr << #x << " = " << x << endl;
#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define piii    pair<int, pair<int, int>>

struct UnionFind {
        int n;
        vector<int> parent;
        vector<int> rank;
        vector<int> num;
        int find(int x) {
                if (parent[x] == x) return  x;
                return parent[x] = find(parent[x]);
        }
        UnionFind(int n_) {
                n = n_;
                parent.resize(n);
                for (int i = 0; i < n; i ++) parent[i] = i;
                rank.assign(n, 0);
                num.assign(n, 1);
        }
        void unite(int x, int y) {
                if ((x = find(x)) != (y = find(y))) {
                        if (rank[x] < rank[y]) {
                                parent[x] = y;
                                num[y] += num[x];
                        } else {
                                parent[y] = x;
                                if (rank[x] == rank[y]) rank[x] ++;
                                num[x] += num[y];
                        }
                        n --;
                }
        }
        bool same(int x, int y) { return find(x) == find(y); }
        int get() { return n; }
        int get(int x) { return num[find(x)]; }
};

int main() {
        int n;
        cin >> n;
        string s, t;
        cin >> s >> t;
        UnionFind uf(36);
        long long ans = 1;
        for (int i = 0; i < n; i ++) {
                if ('0' <= s[i] && s[i] <= '9' && '0' <= t[i] && t[i] <= '9') {
                        assert(s[i] == t[i]);
                } else if ('0' <= s[i] && s[i] <= '9' && 'A' <= t[i] && t[i] <= 'Z') {
                        uf.unite(s[i] - '0' + 26, t[i] - 'A');
                } else if ('A' <= s[i] && s[i] <= 'Z' && '0' <= t[i] && t[i] <= '9') {
                        uf.unite(s[i] - 'A', t[i] - '0' + 26);
                } else {
                        uf.unite(s[i] - 'A', t[i] - 'A');
                }
        }
        vector<bool> determined(26, false);
        for (int i = 0; i < n; i ++) {
                if (('0' <= s[i] && s[i] <= '9') || ('0' <= t[i] && t[i] <= '9')) continue;
                bool found_number = false;
                for (int j = 0; j <= 9; j ++) {
                        if (uf.same(s[i] - 'A', j + 26)) found_number = true;
                }
                if (found_number) continue;
                if (determined[s[i] - 'A'] || determined[t[i] - 'A']) continue;
                if (i == 0) ans *= 9;
                else ans *= 10;
                determined[s[i] - 'A'] = determined[t[i] - 'A'] = true;
        }
        cout << ans << endl;
        return 0;
}

Submission Info

Judge Result