link to the problem
#include
#include <bits/stdc++.h>
#include
#include
using namespace std;
typedef long long ll;
bool visited[26]={0};
vector ad[26];
void intialize(){
for(ll i=0;i<26;i++){
ad[i].clear();
}
}
void intialize2(){
for(ll i=0;i<26;i++){
visited[i]=0;
}
}
int target;
bool dfs(ll i){
if(i==target) return true;
visited[i]=1;
for(ll j=0;j<ad[i].size();j++){
if(ad[i][j]==target) return true;
if(!visited){
if(dfs(ad[i][j])) return true;
}
}
return false;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(tâ){
string a,b;
cin>>a>>b;
ll m;
cin>>m;
string x;
while(m--){
cin>>x;
ad[x[0]-'a'].push_back(x[3]-'a');
}
if(a.length()!=b.length()){
cout<<"NO"<<endl;
continue;
}
bool decide=0;
for(int i=0;i<a.length();i++){
if(a[i]==b[i]){
continue;
}
target=b[i]-'a';
if(!dfs(a[i]-'a')){decide=1;break;}
intialize2();
}
if(decide){
cout<<"NO"<<endl;
}
else{
cout<<"YES"<<endl;
}
intialize();
}
}
Please format your code properly.
Also, I tried the same approach, and I am getting WA.
Can someone help? @ssrivastava990 @therealnishuz
1 Like
Iâll try this after the codeforces round
1 Like
xD. I was there too. How did yours go?
1 Like
This round was a scam. The problems were terrible. B and Câs statements were very unclear. I always click on âcomplete problemsetâ so that I can view all the problems at once. They didnât even announce that they updated the images in B, which sucked because I wasted the whole duration on B thinking that I was close (I actually was) and assumed that there was nothing wrong with the images. Thatâs why I was wondering how so many people were able to solve it. C was also not clear and I never even attempt (I canât) anything above C in div 2s. I ended up doing only A in the round with 488 points. Now that theyâve updated B completely, itâs really easy.
This was the worst codeforces round. Completely unexpected.
1 Like
Argh! Thatâs sad. And it was very surprising. Problems A, B, and C had O(1) solutions. I liked solving D though. And I didnât even realize there was trouble with Problem B images until now
1 Like
Instead of 6 ticks, there were only 4 in the beginning.
1 Like
Ouch. Thatâs very misleading.
1 Like
For this question, if |S| \neq |T|, the answer is no, right?
Yep. Directly "NO.
This got accepted, but this is a slightly different dfs logic. However, Iâd like to find out why the bool dfs()
version was failing.
1 Like
Haha, thatâs the exact train of thought that I went through. But you can change âaâ to âbâ, even if there is no direct mapping. Like, itâs still possible if we have a->t and t->b maps. Hence, dfs.
1 Like
Well. not necessarily.
s = ab
t = xy
6
a->t
b->t
t->x
t->y
Realized this after my epic fail â here
1 Like
The problem with this code is if |S| \neq |T|, your function doesnât take in m and the mappings because you return nothing from the function immediately. This input gets piled up and goes to the next test cases where your program gets messed up.
1 Like
ARGHHHHHHHHHHHH! I cannot believe I did this again. You have a really good eye! Thank you so much!
1 Like
I can sleep in peace. AC.
I was also not clearing the adjacency list by returning immediately.
1 Like
i have checked length after in putting mappings
Can you post your submission link? Itâs hard to see what youâve done here.