제출 #1175818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175818		nuutsnoynton	Zamjene (COCI16_zamjene)	C++20	0 / 140	6096 ms	47256 KiB

zamjene

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 1e6 + 2;
const ll M = 37;
const ll mod = 1e15+43;
ll a[N], b[N], ataman[N], sz[N], val[N], val1[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) swap(x, y);
	if (x > y) swap(x, y);
	ataman[y] =x ;
	val[x] += val[y];
	val1[x] += val1[y];
	sz[x] += sz[y];
}

int main() {
	ll n, m, r, x, y, i,i1, j1, j, ans, t, q, type, x1, y1, s;

	cin >> n >> q;
	
	a[0] = 0;
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
		a[i] = Pow(M, a[i]);
		b[i] = a[i];
		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 ++) {
		val1[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];
			continue;
		}
		if ( type == 2) {
			cin >> x >> y;
			Unite(x, y);
			continue;
		}
		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] != val1[i1] && val[j1] != val1[j1] && ll(val[i1] ^ val[j1]) == ll(val1[i1] ^ val1[j1])) {
					ans ++;
				}
			}
		}
		if ( type == 3) {
			if ( ans == 0) cout << "DA" << endl;
			else cout << "NE" << endl;
		}
		if ( type == 4) {
			cout << ans << endl;
		}
		
		
	}	
	
}

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