제출 #1309722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309722		quollcucumber`	Bliskost (COI23_bliskost)	C++20	0 / 100	1117 ms	483144 KiB

Main

#include <bits/stdc++.h>
#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;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 43