This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define int long long
using namespace std;
const int N=6e4,M=2e3+10,mod=100000000000031;
vector<int>v;
long long summ(long long x,long long y){
return ((x%mod)+(y%mod))%mod;
}
long long mult(long long x,long long y){
return ((x%mod)*(y%mod))%mod;
}
string a[N],b[N];
map< string ,string > p;
map<string,int>sz;
string root(string i)
{
if(p[i]!=p[p[i]])
p[i]=root(p[i]);
return p[i];
}
void onion(string x,string y){
x=root(x);
y=root(y);
if(x==y)
return ;
if(sz[x]<sz[y])
swap(x,y);
p[y]=x;
sz[x]+=sz[y];
}
bool okk(string s){
return (s[0]>='a'&&s[0]<='z');
}
main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
cin>>b[i];
for(int i=0;i<n;i++)
p[a[i]]=a[i],p[b[i]]=b[i],sz[a[i]]=0,sz[b[i]]=0;
int ok=0;
for(int i=0;i<n;i++)
if(okk(a[i])&&okk(b[i])){
onion(a[i],b[i]);
}
for(int i=0;i<n;i++){
if(!okk(a[i]))
sz[a[i]]=100001;
if(!okk(b[i]))
sz[b[i]]=100001;
}
for(int i=0;i<n;i++){
if(!okk(a[i])&&okk(b[i]))
onion(b[i],a[i]);
else if(okk(a[i])&&!okk(b[i]))
onion(b[i],a[i]);
}
for(int i=0;i<n;i++){
if(okk(a[i])){
string x=root(a[i]);
if(!okk(x))
a[i]=x;
else a[i]="1";
}
if(okk(b[i])){
string x=root(b[i]);
if(!okk(x))
b[i]=x;
else b[i]="1";
}
}
for(int i=0;i<n;i++)
if(a[i]!=b[i])
ok=1;
if(ok==1)
cout<<"NE"<<endl;
else cout<<"DA"<<endl;
return 0;
}
/*
4
4 5 iks ipsilon
1 iks 3 iks
5
x 3 x y 3
x y 2 z 3
*/
Compilation message (stderr)
zamjena.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
48 | main()
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |