#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3qplfh5 ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define nare {cout<<"NE\n"; exit(0);}
#define yare {cout<<"YES\n"; exit(0);}
using namespace std;
typedef long long ll;
typedef long double ld;
void print(){
cout<<"\n";
}
template<class te,class ...ti>
void print(const te&v, const ti&...nv) {
cout<<v;
if(sizeof...(nv)){
cout<<" ";
print(nv...);
}
}
using tpii=pair<int,pair<int,int>>;
using pii=pair<int,int>;
using vi=vector<int>;
using vll=vector<long long>;
const int _n=1e5+11;
ll toint(string s){
ll x=0,pot=1;
drep(i,sz(s)){
x+=pot*(s[i]-'0');
pot*=10ll;
}
return x;
}
struct dsu{
int n,size_;
vector<int> par,siz,color;
dsu(int m){
init(m);
}
void init(int m){
n=m;
size_=m;
par.resize(n,0);
siz.resize(n,0);
color.resize(n,0);
for(int i=0;i<n;i++){
par[i]=i;
siz[i]=1;
color[i]=-1;
}
}
void merge(int x,int y,int type=0){
int a=parent(x),b=parent(y);
if(a==b) return;
size_--;
if(siz[a]<siz[b]) swap(a,b);
siz[a]+=siz[b];
par[b]=a;
}
int parent(int x){
return par[x]==x?x:parent(par[x]);
}
bool same(int x, int y){
return parent(x)==parent(y);
}
int size(){
return size_;
}
};
void slv(){
int n;
cin>>n;
std::map<string,vec(pii)> mp;
vi a,b;
rep(t,2){
rep(i,n){
string s;
cin>>s;
if(s[0]>='0' and s[0]<'9'){
b.pb(toint(s));
}else{
mp[s].pb({t,i});
b.pb(-1);
}
}
if(t==0){
a=b;
b={};
}
}
{
int i=1001;
for(auto p : mp){
for(auto _p : p.se){
if(_p.fi) b[_p.se]=i;
else a[_p.se]=i;
}
i++;
}
}
dsu uf(_n);
rep(i,n){
int x=a[i],y=b[i];
if(x<=1000){
if(y<=1000){
if(x!=y){
nare;
}
}else{
uf.merge(x,y);
}
}else{
uf.merge(x,y);
}
}
rep(i,n){
int x=a[i],y=b[i];
int up=uf.parent(x);
if(x<=1000){
uf.color[up]=x;
}
up=uf.parent(y);
if(y<=1000){
uf.color[up]=y;
}
}
int j=1001;
rep(i,n){
int x=a[i],y=b[i];
int up=uf.parent(x);
if(uf.color[up]==-1 and x==uf.parent(x)){
uf.color[up]=j;
j++;
}
up=uf.parent(y);
if(uf.color[up]==-1 and y==uf.parent(y)){
uf.color[up]=j;
j++;
}
}
rep(i,n){
int x=a[i];
if(x<=1000 and uf.color[uf.parent(x)]!=x){
nare;
}
a[i]=uf.color[uf.parent(x)];
}
rep(i,n){
int x=b[i];
if(x<=1000 and uf.color[uf.parent(x)]!=x){
nare;
}
b[i]=uf.color[uf.parent(x)];
}
rep(i,n){
if(a[i]!=b[i]){
nare;
}
}
yare;
// rep(i,n){
// print(a[i],'\0');
// }
// print('\n');
// rep(i,n){
// print(b[i],'\0');
// }
// print('\n');
}
int main(){
_3qplfh5;
int t=1;
// cin>>t;
slv();
//
return 0;
}
Compilation message
zamjena.cpp: In function 'int main()':
zamjena.cpp:186:6: warning: unused variable 't' [-Wunused-variable]
186 | int t=1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
2496 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
3692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
