oj.uz

Submission #503370

# Submission time Handle Problem Language Result Execution time Memory
503370 2022-01-07T17:55:25 Z inksamurai Zamjena (COCI18_zamjena) C++17
70 / 70
 59 ms 8180 KB 
#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<<"DA\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;
      |      ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 1 ms 1460 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1456 KB Output is correct
5 Correct 1 ms 1488 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1496 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1464 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 2 ms 1596 KB Output is correct
3 Correct 3 ms 1724 KB Output is correct
4 Correct 3 ms 1860 KB Output is correct
5 Correct 3 ms 1868 KB Output is correct
6 Correct 3 ms 1740 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2388 KB Output is correct
2 Correct 17 ms 3524 KB Output is correct
3 Correct 28 ms 5172 KB Output is correct
4 Correct 32 ms 5652 KB Output is correct
5 Correct 59 ms 8180 KB Output is correct
6 Correct 41 ms 5724 KB Output is correct