| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1309723 | quollcucumber` | Bliskost (COI23_bliskost) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#pragma GCC target("axv2")
#define int long long
using namespace std;
int parent[11881476];
int num(string s) {
int total = 0;
for(char i : s) {
total *= 26;
total += i - 'a';
}
return total;
}
int dsu(int n) {
if(parent[n] == n) return n;
return parent[n] = dsu(parent[n]);
}
signed main(){
for(int i = 0; i < pow(26,5)+100; i++) parent[i] = i;
int n, q;
cin >> n >> q;
queue<string> que;
que.push("");
for(int i = 0; i < n; i++) {
int sz = que.size();
for(int j = 0; j < sz; j++) {
string s = que.front();
que.pop();
for(int k = 0; k < 26; k++) {
string st = s;
st += 'a' + k;
que.push(st);
}
}
}
while(!que.empty()) {
string str = que.front();
que.pop();
string newstr = str;
newstr[0]++;
newstr[1]++;
if(newstr[0] == 'z' + 1) newstr[0] = 'a';
if(newstr[1] == 'z' + 1) newstr[1] = 'a';
parent[dsu(num(str))] = dsu(num(newstr));
newstr[0]--;
newstr[2]++;
if(newstr[0] == 'a'-1) newstr[0] = 'z';
if(newstr[2] == 'z' + 1) newstr[2] = 'a';
parent[dsu(num(str))] = dsu(num(newstr));
newstr[1]--;
newstr[3]++;
if(newstr[1] == 'a'-1) newstr[1] = 'z';
if(newstr[3] == 'z' + 1) newstr[3] = 'a';
parent[dsu(num(str))] = dsu(num(newstr));
newstr[2]--;
newstr[4]++;
if(newstr[2] == 'a'-1) newstr[2] = 'z';
if(newstr[4] == 'z' + 1) newstr[4] = 'a';
parent[dsu(num(newstr))] = dsu(num(str));
}
string a , b;
cin >> a>> b;
if(dsu(num(a)) == dsu(num(b))) {
cout<<"da\n";
}else{
cout<<"ne\n";
}
for(int i = 0; i < q; i++) {
int pos; char c;
cin >> pos >> c;
pos--;
a[pos] = c;
if(dsu(num(a)) == dsu(num(b))) {
cout<<"da\n";
}else {
cout<<"ne\n";
}
}
return 0;
}