Submission #1175842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175842		nuutsnoynton	Zamjene (COCI16_zamjene)	C++20	70 / 140	6096 ms	39556 KiB

zamjene

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 1e6 + 2;
const ll M = 43;
const ll mod = 1e14+7;
ll a[N], b[N], ataman[N], sz[N], val[N];
map < ll, ll > cnt1, cnt2;
ll Pow(ll a, ll b) {
	if ( b == 0) return 1;
	if ( b == 1) return a % mod;
	ll r = Pow(a, b/2);
	r = r * r %mod;
	if ( b % 2 == 1) r = r * a %mod;
	return r;
}

ll Get(ll x) {
	if ( x == ataman[x]) return x;
	return ataman[x] = Get(ataman[x]);
}

void Unite(ll x, ll y) {
	x = Get(x);
	y = Get(y);
	if ( x == y)return ;
	if (x > y) swap(x, y);
	ataman[y] =x ;
	
	val[x] += val[y];
	sz[x] += sz[y];
}

int main() {
//	ios::sync_with_stdio(0);
//	cin.tie(0);
///	cout.tie(0);
	ll n, m, r, x, y, i,i1, j1, j, ans, t, q, type, x1, y1, s;

	cin >> n >> q;
	
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
		b[i]=  a[i];
		a[i] = Pow(M, a[i] + 1) ;
		ataman[i] = i;
		sz[i] = 1;
		val[i] += a[i];
	//	cout << a[i] << " ";
	}
	sort ( b + 1, b + n + 1);
	for (i = 1; i <= n; i ++) {
		b[i] = Pow(M, b[i] + 1);
		val[i] -= b[i];
	}
	ans = 0;

	while (q --) {
		cin >> type;
		if ( type == 1) {
			cin >> x >> y;
			x1 = Get(x);
			y1 = Get(y);
			val[x1] -= a[x];
			val[y1] += a[x];
			val[x1] += a[y];
			val[y1] -= a[y];
			swap(a[x], a[y]);
			continue;
		}
		if ( type == 2) {
			cin >> x >> y;
			Unite(x, y);
			continue;
		}
		
		if ( type == 3) {
			ans = 0;
			for (i = 1; i<= n; i++) {
				r = Get(i);
				if (val[r] != 0) ans = 1;
			}
			if ( ans == 0) cout << "DA" << "\n";
			else cout << "NE" << "\n";
			continue;
		}
		if ( type == 4) {
			ans = 0;
		for (i = 1; i <= n; i++) {
			for (j = i + 1; j <= n; j ++) {
				i1 = Get(i);
				j1 = Get(j);
				if ( i1 == j1 ) continue;
				if ( val[i1] != 0 && val[j1] !=  0 && (val[i1] + val[j1]) == 0) {
					ans ++;
				}
			}
		}
			cout << ans << "\n";
		}
		
		
	}	
	
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14