제출 #861209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861209		beaboss	Zamjene (COCI16_zamjene)	C++14	0 / 140	1386 ms	74244 KiB

zamjene

// Source: https://oj.uz/problem/view/COCI16_zamjene
//  

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

map<ll, ll> other;
ll bad = 0;

ll merges = 0;

const ll N = 1e6 + 10;
ll in[N];
ll out[N];

ll multi[N];
ll a[N];

ll random(ll a, ll b) {
	return a + rand()% (b - a + 1);
}

ll MOD = random(1e8, 1e9 + 7);

struct DSU {
	vector<ll> e;
	DSU(ll N) { e = vector<ll>(N, -1);}

	// get representive component (uses path compression)
	ll get(ll x) {
		if (e[x] < 0) return x;
		else {
			e[x] = get(e[x]);

			return e[x];
		}
	}

	bool same_set(ll a, ll b) { return get(a) == get(b); }

	ll size(ll x) { return -e[get(x)]; }

	void rem(ll val) {
		// cout << val << endl;
		val = get(val);

		if (out[val] != in[val]) bad--;

		assert(other[(out[val] - in[val] + MOD) % MOD]);
		other[(out[val] - in[val] + MOD) % MOD] -= size(val);


		if (out[val] != in[val]) merges -= other[(in[val] - out[val] + MOD) % MOD] * size(val);

		
		
	}

	void add(ll val) {
		val = get(val);
		if (out[val] != in[val]) bad++;


		if (out[val] != in[val]) merges += other[(in[val] - out[val] + MOD) % MOD] * size(val);
		// cout << ' ' << other[(in[val] - out[val] + MOD) % MOD] * size(val) << endl;
		other[(out[val] - in[val] + MOD) % MOD] += size(val);

		
		
	}

	bool unite(ll x, ll y) {  // union by size
		
		// if (x < y) swap(x, y);
		// cout << ' ' << merges << endl;
		
		// cout << ' ' << merges << endl;


		x = get(x), y = get(y);
		
		if (x == y) return false;
		
		rem(x);
		rem(y);
		
		if (-e[x] > -e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x;

		in[x] = (in[x] + in[y]) % MOD;
		out[x] = (out[y] + out[x]) % MOD;

		add(x);
		
		return true;
	}

	void switch_(ll x, ll y) {
		rem(x);
		rem(y);

		out[x] = (out[x]+multi[a[y]] - multi[a[x]]) % MOD;
		out[y] = (out[y]+multi[a[x]] - multi[a[y]]) % MOD;


		// cout << x << y << out[x] << out[y] << endl;
		add(x);
		add(y);

		swap(a[x], a[y]);
	}
};

DSU dsu(N);


ll b[N];




int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	ll n,q;
	cin >> n >> q;


	FOR(i, 1, n + 1) {
		ll d;
		cin >> d;
		if (multi[d] == 0) multi[d] = random(1000, 5000);

		out[i] = multi[d];
		a[i]=d;
		b[i] = d;
	}

	sort(b + 1, b + n + 1);

	FOR(i, 1, n + 1) in[i] = multi[b[i]];

	FOR(i, 1, n+1)
		dsu.add(i);

	FOR(i, 0, q) {
		ll t;
		cin >> t;
		if (t == 1) {
			ll a, b;
			cin >> a >> b;
			dsu.switch_(a, b);
		} else if (t == 2) {
			ll a, b;
			cin >> a >> b;
			dsu.unite(a, b);
		} else if (t == 3) {
			if (bad) cout << "NE" << endl;
			else cout << "DA" << endl;
			// cout << bad > 0 ? "NE" : "DA" << endl;
		} else {
			cout << merges << 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