QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#740996#9726. AUSTMM233#WA 1ms3820kbC++232.7kb2024-11-13 12:52:102024-11-13 12:52:11

Judging History

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

  • [2024-11-13 12:52:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3820kb
  • [2024-11-13 12:52:10]
  • 提交

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'