QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#751503#9726. AUSProaes#RE 0ms3564kbC++202.9kb2024-11-15 19:11:132024-11-15 19:11:13

Judging History

你现在查看的是最新测评结果

  • [2024-11-15 19:11:13]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3564kb
  • [2024-11-15 19:11:13]
  • 提交

answer

/**
 *    title:  aa.cpp
 *    author:  Proaes Meluam
 *    created:  2024-11-15 18:48:11
**/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h" 
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long;
using ull = unsigned long long;
const double pi = acos(-1);
const double E = exp(1);
constexpr ll mod = 1e9 + 7;
// constexpr int inf = 0x3f3f3f3f;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    const int m = 3;
    int tt = 1;
    cin >> tt;
    while (tt--) {
        vector<string> s(m + 10);
        vector<int> len(m + 10);
        for (int i = 1; i <= m; ++ i) {
            cin >> s[i];
            len[i] = s[i].size();
            s[i] = " " + s[i];
        }
        if (len[1] != len[2]) {
            cout << "NO\n";
        } else {
            if (len[1] != len[3]) {
                cout << "YES\n";
            } else {
                bool flag = 0;
                int n = len[1];
                vector<ll> dsu(260 + 1); // dsu[i]存是 i 的祖宗结点(未必路径压缩好了,所以求祖宗结点需调用find函数)
                vector<ll> dsus(260 + 1 , 1); // dsus[i]存 i 所在图的大小
                iota(dsu.begin(), dsu.end(), 0);
                auto find = [&](auto self, ll a) {
                    if (a == dsu[a]) {
                        return a;
                    } else {
                        dsu[a] = self(self, dsu[a]);
                        return dsu[a];
                    }
                };

                auto merge = [&](ll a, ll b) {
                    int x = find(find, a);
                    int y = find(find, b);
                    if (x != y) {
                        if (dsus[x] < dsus[y]) {
                            swap(x, y);
                        }
                        dsu[y] = x;
                        dsus[x] += dsus[y];
                    }
                };

                vector<vector<int>> a(m + 20, vector<int>(n + 10));
                for (int i = 1; i <= m; ++ i) {
                    for (int j = 1; j <= n; ++ j) {
                        a[i][j] = s[i][j] - 'a';
                    }
                }

                for (int i = 1; i <= n; ++ i) {
                    merge(a[1][i], a[2][i]);
                }
                for (int i = 1; i <= n; ++ i) {
                    dsu[i] = find(find, dsu[i]);
                }

                for (int i = 1; i <= n; ++ i) {
                    if (dsu[a[1][i]] != dsu[a[3][i]] || dsu[a[2][i]] != dsu[a[3][i]]) {
                        flag = 1;
                    }
                }
                if (flag == 1) {
                    cout << "YES\n";
                } else {
                    cout << "NO\n";
                }
            }
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3564kb

input:

4
abab
cdcd
abce
abab
cdcd
abcd
abab
cdcd
abc
x
yz
def

output:

YES
NO
YES
NO

result:

ok 4 lines

Test #2:

score: -100
Runtime Error

input:

10
ekkzjwextuoazxsosiiiditwrjiztfvxtzaztmdfhxroaqkjcdgsgiitkfglcrtgjquspjyjtodyhxetldbhvxampcvbinzgksxkunduhvbddakqswurshbnuazthfnxmsuyypznmxmatsnvpqovscnkkcjphtcmcsqteeikwggnugskjjwttvlrxmmrkyltxjhfiqicttcfumurdrmiqauruywgdomxxpbeunliyvsutrneexoyckjflhnmmaaovxubnptlemptxbhrflbnfcowktydgbugdxvkvegza...

output:


result: