Submission #1692573


Source Code Expand

#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;

class UnionFind{
	vector<int> par, rnk;
	public:
	UnionFind(int n){
		par=vector<int>(n);
		rnk=vector<int>(n,0);
		for(int i=0; i<n; i++) par[i]=i;
	}
	int root(int i){
		if(par[i]==i) return i;
		return par[i]=root(par[i]);
	}
	void unite(int i, int j){
		int ri = root(i);
		int rj = root(j);
		if(ri==rj) return;

		if(rnk[ri]==rnk[rj]){
			par[ri] = rj;
			rnk[rj]++;
		}
		else if(rnk[ri] < rnk[rj]){
			par[ri] = rj;
		}
		else{
			par[rj] = ri;
		}
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
};

bool is_digit(char c){
	return '0' <= c && c <= '9';
}

int main(){
	int N;
	string s1, s2;

	cin >> N;
	cin >> s1 >> s2;

	UnionFind uf(27);

	vector<bool> used(26);
	for(int i=0; i<N; i++){
		if(!is_digit(s1[i]) && !is_digit(s2[i])){
			uf.unite(s1[i]-'A', s2[i]-'A');
		}
		else if(is_digit(s1[i]) && !is_digit(s2[i])){
			uf.unite(s2[i]-'A', 26);
		}
		else if(!is_digit(s1[i]) && is_digit(s2[i])){
			uf.unite(s1[i]-'A', 26);
		}

		if(!is_digit(s1[i])){
			used[s1[i]-'A'] = true;
		}
		if(!is_digit(s2[i])){
			used[s2[i]-'A'] = true;
		}
	}

	for(int i=0; i<26; i++){
		for(int j=i+1; j<26; j++){
			if(uf.same(i, j)){
				used[j] = false;
			}
		}
		if(uf.same(i, 26)){
			used[i] = false;
		}
	}


	int n = 0;
	for(int i=0; i<26; i++){
		n += used[i] ? 1 : 0;
	}


	ll x = 1;
	if(s1[0] != s2[0] && !is_digit(s1[0]) && used[s1[0]-'A'] && !is_digit(s2[0]) && used[s2[0]-'A']){
		x *= 81;
		n -= 2;
	}
	else if(!is_digit(s1[0]) && used[s1[0]-'A'] || !is_digit(s2[0]) && used[s2[0]-'A']){
		x *= 9;
		n--;
	}

	for(int i=0; i<n; i++) x *= 10;
	cout << x << endl;

	return 0;
}

Submission Info

Submission Time
Task B - 大事な数なのでZ回書きまLた。
User emak
Language C++ (G++ 4.6.4)
Score 100
Code Size 1806 Byte
Status AC
Exec Time 5 ms
Memory 640 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 3
AC × 29
AC × 55
Set Name Test Cases
Sample subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt
Subtask1 subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt
Subtask2 subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt
Case Name Status Exec Time Memory
subtask0-sample01.txt AC 5 ms 640 KB
subtask0-sample02.txt AC 1 ms 256 KB
subtask0-sample03.txt AC 1 ms 256 KB
subtask1-01.txt AC 1 ms 256 KB
subtask1-02.txt AC 1 ms 256 KB
subtask1-03.txt AC 1 ms 256 KB
subtask1-04.txt AC 1 ms 256 KB
subtask1-05.txt AC 1 ms 256 KB
subtask1-06.txt AC 1 ms 256 KB
subtask1-07.txt AC 1 ms 256 KB
subtask1-08.txt AC 1 ms 256 KB
subtask1-09.txt AC 1 ms 256 KB
subtask1-10.txt AC 1 ms 256 KB
subtask1-11.txt AC 1 ms 256 KB
subtask1-12.txt AC 1 ms 256 KB
subtask1-13.txt AC 1 ms 256 KB
subtask1-14.txt AC 1 ms 256 KB
subtask1-15.txt AC 1 ms 256 KB
subtask1-16.txt AC 1 ms 256 KB
subtask1-17.txt AC 1 ms 256 KB
subtask1-18.txt AC 1 ms 256 KB
subtask1-19.txt AC 1 ms 256 KB
subtask1-20.txt AC 1 ms 256 KB
subtask1-21.txt AC 1 ms 256 KB
subtask1-22.txt AC 1 ms 256 KB
subtask1-23.txt AC 1 ms 256 KB
subtask1-24.txt AC 1 ms 256 KB
subtask1-25.txt AC 1 ms 256 KB
subtask1-26.txt AC 1 ms 256 KB
subtask2-01.txt AC 1 ms 256 KB
subtask2-02.txt AC 1 ms 256 KB
subtask2-03.txt AC 1 ms 256 KB
subtask2-04.txt AC 1 ms 256 KB
subtask2-05.txt AC 1 ms 256 KB
subtask2-06.txt AC 1 ms 256 KB
subtask2-07.txt AC 1 ms 256 KB
subtask2-08.txt AC 1 ms 256 KB
subtask2-09.txt AC 1 ms 256 KB
subtask2-10.txt AC 1 ms 256 KB
subtask2-11.txt AC 1 ms 256 KB
subtask2-12.txt AC 1 ms 256 KB
subtask2-13.txt AC 1 ms 256 KB
subtask2-14.txt AC 1 ms 256 KB
subtask2-15.txt AC 1 ms 256 KB
subtask2-16.txt AC 1 ms 256 KB
subtask2-17.txt AC 1 ms 256 KB
subtask2-18.txt AC 1 ms 256 KB
subtask2-19.txt AC 1 ms 256 KB
subtask2-20.txt AC 1 ms 256 KB
subtask2-21.txt AC 1 ms 256 KB
subtask2-22.txt AC 1 ms 256 KB
subtask2-23.txt AC 1 ms 256 KB
subtask2-24.txt AC 1 ms 256 KB
subtask2-25.txt AC 1 ms 256 KB
subtask2-26.txt AC 1 ms 256 KB