QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#751482 | #9726. AUS | Proaes# | RE | 0ms | 3560kb | C++20 | 2.8kb | 2024-11-15 19:02:19 | 2024-11-15 19:02:20 |
Judging History
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...