Submission #161695

#	Time	Username	Problem	Language	Result	Execution time	Memory
161695		eggag32	Zamjena (COCI18_zamjena)	C++17	14 / 70	9 ms	2168 KiB

zamjena

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int num(string s){
	int n = s.size();
	rep(i, n){
		if(!(s[i] >= '0' && s[i] <= '9')){
			//it is not a number
			return 0;
		}
	}
	int num1 = 0;
	int mult = 1;
	reverse(all(s));
	rep(i, n){
		num1 += (s[i] - '0') * mult;
		mult *= 10;
	}
	return num1;
}

int sum(string s){
	int n = s.size();
	int s1 = 0;
	rep(i, n){
		s1 += (s[i] - 'a') + 1;
	}
	return s1;
}

struct DSU{
	int S;
	struct node{
		int parent; ll sum;
	};
	vector<node> dsu;
	DSU(int n){
		S = n;
		rep(i, n){
			node tmp;
			tmp.parent = i; tmp.sum = 0;
			dsu.pb(tmp);
		}
	}
	void reset(int n){
		dsu.clear();
		S = n;
		rep(i, n){
			node tmp;
			tmp.parent = i; tmp.sum = 1;
			dsu.pb(tmp);
		}
	}
	int root(int u){
		if(dsu[u].parent == u) return u;
		dsu[u].parent = root(dsu[u].parent);
		return dsu[u].parent;
	}
	void merge(int u, int v){
		u = root(u); v = root(v);
		if(u == v) return;
	//	if(getsum(u) < getsum(v)) swap(u, v);
		dsu[v].parent = u;
	//	dsu[u].sum += dsu[v].sum;
	}
	bool sameset(int u, int v){
		if(root(u) == root(v)) return true;
		return false;
	}
	ll getsum(int u){
		return dsu[root(u)].sum;
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n;
	cin >> n;
	vector<string> s(n), s1(n);
	rep(i, n) cin >> s[i];
	rep(i, n) cin >> s1[i];
	DSU dsu(12205);
	rep(i, n){
		int tmp = num(s[i]);
		int tmp1 = num(s1[i]);
		if(tmp){
			if(tmp1){
				if(tmp != tmp1){
					cout << "NE" << endl;
					return 0;
				}
			}
			else{
				int sm1 = sum(s1[i]);
				if(!dsu.dsu[sm1].sum) dsu.dsu[sm1].sum = tmp;
				else{
					if(tmp != dsu.dsu[sm1].sum){
						cout << "NE" << endl;
						return 0;
					}
				}
			}
		}
		else{
			if(tmp1){
				int sm1 = sum(s[i]);
				if(!dsu.dsu[sm1].sum) dsu.dsu[sm1].sum = tmp1;
				else{
					if(tmp1 != dsu.dsu[sm1].sum){
						cout << "NE" << endl;
						return 0;
					}
				}
			}
			else{
				int sm = sum(s[i]);		
				int sm1 = sum(s[i]);		
				dsu.merge(sm, sm1);
			}
		}
	}
	cout << "DA" << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14