Submission #1842079

---

Source Code Expand

#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cmath>
#include <vector>
#include <fstream>
#include <string>
#include <random>
#include <queue>
#include <iomanip>
#include <functional>
#include <climits>

using namespace std;

using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vll = std::vector<ll>;
using vpll = std::vector<pll>;
using vpii = std::vector<pii>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vvpii = std::vector<vpii>;

const ll mod197 = 1000000007LL;
const ll INF = 200LL * 200 * 100000 + 10;

const double PI11 = 3.14159265359;


class union_find {
public:
	int par[100010] = {};
	int rank[100010] = {};

	void init(int n) {
		for (int i = 0; i < n; i++) {
			par[i] = i;
			rank[i] = 0;
		}
	}

	int find(int x) {
		if (par[x] == x) {
			return x;
		}
		else {
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y) {
		x = find(x);
		y = find(y);

		if (x == y) return;

		if (rank[x] < rank[y]) {
			par[x] = y;
		}
		else {
			par[y] = x;
			if (rank[x] == rank[y]) rank[x] ++;
		}
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

};

int main(void)
{
	//0-9 , 'A' - 'Z'

	union_find uf;
	uf.init(1000);

	int n;
	string strs[2];
	cin >> n;

	for (int i = 0; i < 2; i++) {
		cin >> strs[i];
	}

	for (int i = 0; i < n; i++) {
		uf.unite(strs[0][i],strs[1][i]);
	}

	bool not_zero = false;

	ll answer = 1;

	for (int i = 0; i < n; i++) {
		if (strs[0][i] >= '0' && strs[0][i] <= '9') {
			cerr << strs[0][i];
			if (strs[0][i] >= '1')
				not_zero = true;
		}
		else {
			if ([&]() {
				for (int j = 0; j < 10; j++) {
					if (uf.same(strs[0][i], j + '0')) {
						cerr << (char)(j + '0');
						return false;
					}
				}
				return true;
			}()) {
				if (uf.same(strs[0][i],1)) {
					cerr << '*';
				}
				else {
					cerr << '?';
					uf.unite(strs[0][i], 1);
					if (not_zero) {
						answer *= 10;
					}
					else {
						answer *= 9;
						not_zero = true;
					}
				}
			}
		}
	}

	cerr << endl;

	cout << answer << endl;

	return 0;
}

Submission Info

Judge Result