QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#750197#9726. AUS552Hz#TL 0ms3664kbC++171.3kb2024-11-15 13:22:112024-11-15 13:22:12

Judging History

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

  • [2024-11-15 13:22:12]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3664kb
  • [2024-11-15 13:22:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cout<<#x<<": "<<x<<endl
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll=long long;
using ull=unsigned long long;
void solve(){
    string a,b,c;
    cin>>a>>b>>c;
    if(a.size()!=b.size()){
        cout<<"NO"<<endl;
        return;
    }
    vector<int> f(26);
    for(int i=0;i<26;i++)
        f[i]=i;
    for(int i=0;i<a.size();i++){
        if(a[i]!=b[i]){
            int x=a[i]-'a',y=b[i]-'a';
            if(f[x]==f[y])
                continue;
            else
                f[y]=x;
        }
    }
    if(c.size()!=a.size()){
        cout<<"YES"<<endl;
        return;
    }
    for(int i=0;i<a.size();i++){
        int cur=a[i]-'a';
        while(f[cur]!=cur)
            cur=f[cur];
        a[i]='a'+cur;
    }
    for(int i=0;i<c.size();i++){
        int cur=c[i]-'a';
        while(f[cur]!=cur)
            cur=f[cur];
        c[i]='a'+cur;
    }   
    if(a==c)
        cout<<"NO"<<endl;
    else
        cout<<"YES"<<endl; 
}
signed main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}
/*
贡献法
正难则反
数小状压
关系连边
拆位
广义单调性
最长转最短
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Time Limit Exceeded

input:

10
ekkzjwextuoazxsosiiiditwrjiztfvxtzaztmdfhxroaqkjcdgsgiitkfglcrtgjquspjyjtodyhxetldbhvxampcvbinzgksxkunduhvbddakqswurshbnuazthfnxmsuyypznmxmatsnvpqovscnkkcjphtcmcsqteeikwggnugskjjwttvlrxmmrkyltxjhfiqicttcfumurdrmiqauruywgdomxxpbeunliyvsutrneexoyckjflhnmmaaovxubnptlemptxbhrflbnfcowktydgbugdxvkvegza...

output:


result: