제출 #861208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861208		beaboss	Zamjene (COCI16_zamjene)	C++14	0 / 140	1146 ms	36064 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<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

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

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

int merges = 0;

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

int multi[N];
int a[N];

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

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

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

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

			return e[x];
		}
	}

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

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

	void rem(int 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(int 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(int x, int 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_(int x, int 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);


int b[N];




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

	int n,q;
	cin >> n >> q;


	FOR(i, 1, n + 1) {
		int d;
		cin >> d;
		if (multi[d] == 0) multi[d] = random(10, 500);

		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) {
		int t;
		cin >> t;
		if (t == 1) {
			int a, b;
			cin >> a >> b;
			dsu.switch_(a, b);
		} else if (t == 2) {
			int 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