QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#740996 | #9726. AUS | TMM233# | WA | 1ms | 3820kb | C++23 | 2.7kb | 2024-11-13 12:52:10 | 2024-11-13 12:52:11 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn= 1e6+5;
struct DSU
{
vector<int> fa,siz;
void init(int n)
{
fa.resize(n);
iota(fa.begin(),fa.end(),0);
siz.assign(n,1);
}
DSU(int n) {init(n);}
int find(int x)
{
while(x!=fa[x])
x=fa[x]=fa[fa[x]];
return x;
}
bool merge(int x,int y)
{
x=find(x),y=find(y);
if(x==y) return false;
siz[y]+=siz[x];
fa[x]=y;
return true;
}
};
void solve()
{
string s[3];cin>>s[0]>>s[1]>>s[2];
if(s[0].size()!=s[1].size()&&s[0].size()!=s[2].size()&&s[1].size()!=s[2].size())
{
cout<<"NO\n";
return ;
}
if(s[0].size()==s[1].size()&&s[1].size()==s[2].size())
{
int n=s[0].size();
{
string ss[3];
DSU dsu(26);
ss[0]=s[0],ss[1]=s[1],ss[2]=s[2];
for(int i=0;i<n;i++)
{
dsu.merge(s[0][i]-'a',s[1][i]-'a');
}
for(int i=0;i<n;i++)
{
ss[0][i]=('a'+dsu.find(s[0][i]-'a'));
ss[1][i]=('a'+dsu.find(s[1][i]-'a'));
ss[2][i]=('a'+dsu.find(s[2][i]-'a'));
}
if(ss[0]!=ss[2])
{
cout<<"YES\n";
return;
}
}
{
string ss[3];
DSU dsu(26);
ss[0]=s[0],ss[1]=s[1],ss[2]=s[2];
for(int i=0;i<n;i++)
{
dsu.merge(s[0][i]-'a',s[2][i]-'a');
}
for(int i=0;i<n;i++)
{
ss[0][i]=('a'+dsu.find(s[0][i]-'a'));
ss[1][i]=('a'+dsu.find(s[1][i]-'a'));
ss[2][i]=('a'+dsu.find(s[2][i]-'a'));
}
if(ss[0]!=ss[1])
{
cout<<"YES\n";
return;
}
}
{
string ss[3];
DSU dsu(26);
ss[0]=s[0],ss[1]=s[1],ss[2]=s[2];
for(int i=0;i<n;i++)
{
dsu.merge(s[1][i]-'a',s[2][i]-'a');
}
for(int i=0;i<n;i++)
{
ss[0][i]=('a'+dsu.find(s[0][i]-'a'));
ss[1][i]=('a'+dsu.find(s[1][i]-'a'));
ss[2][i]=('a'+dsu.find(s[2][i]-'a'));
}
if(ss[0]!=ss[1])
{
cout<<"YES\n";
return;
}
}
cout<<"NO\n";
return ;
}
cout<<"YES\n";
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0) ;
int t=1;
cin>>t;
while(t--)solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
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
Wrong Answer
time: 1ms
memory: 3820kb
input:
10 ekkzjwextuoazxsosiiiditwrjiztfvxtzaztmdfhxroaqkjcdgsgiitkfglcrtgjquspjyjtodyhxetldbhvxampcvbinzgksxkunduhvbddakqswurshbnuazthfnxmsuyypznmxmatsnvpqovscnkkcjphtcmcsqteeikwggnugskjjwttvlrxmmrkyltxjhfiqicttcfumurdrmiqauruywgdomxxpbeunliyvsutrneexoyckjflhnmmaaovxubnptlemptxbhrflbnfcowktydgbugdxvkvegza...
output:
NO NO YES NO NO NO NO NO NO NO
result:
wrong answer 3rd lines differ - expected: 'NO', found: 'YES'