QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#751482#9726. AUSProaes#RE 0ms3560kbC++202.8kb2024-11-15 19:02:192024-11-15 19:02:20

Judging History

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

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

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 + 1);
        vector<int> len(m + 1);
        for (int i = 1; i <= m; ++ i) {
            cin >> s[i];
            len[i] = s[i].size();
        }
        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(26 + 1); // dsu[i]存是 i 的祖宗结点(未必路径压缩好了,所以求祖宗结点需调用find函数)
                vector<ll> dsus(26 + 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 + 2, vector<int>(n + 1));
                for (int i = 1; i <= m; ++ i) {
                    for (int j = 1; j <= n; ++ j) {
                        a[i][j] = s[i][j - 1] - '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";
                    
                }
            }
        }
    }
}

详细

Test #1:

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

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: