oj.uz

Submission #161695

# Submission time Handle Problem Language Result Execution time Memory
161695 2019-11-03T18:38:23 Z eggag32 Zamjena (COCI18_zamjena) C++17
14 / 70
 9 ms 2168 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 9 ms 760 KB Output is correct
5 Correct 3 ms 764 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Incorrect 3 ms 760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 764 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Incorrect 2 ms 760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Incorrect 3 ms 888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1400 KB Output is correct
2 Incorrect 7 ms 2168 KB Output isn't correct
3 Halted 0 ms 0 KB -