oj.uz

Submission #861595

# Submission time Handle Problem Language Result Execution time Memory
861595 2023-10-16T14:22:04 Z beaboss Zamjene (COCI16_zamjene) C++14
84 / 140
 4245 ms 149976 KB 
// 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 = 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);

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

		
		
	}

	bool unite(ll x, ll y) {  // union by size


		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) {
		int posx = multi[a[x]];
		int posy = multi[a[y]];
		int oldx = x;
		int oldy = y;
		x = get(x);
		y = get(y);

		rem(x);
		rem(y);
		

		out[x] = (out[x]+posy - posx + MOD) % MOD;
		out[y] = (out[y]+posx - posy + MOD) % MOD;


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

		swap(a[oldx], a[oldy]);
	}
};

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(1e6, 1e9);

		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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16476 KB Output is correct
2 Correct 3 ms 16476 KB Output is correct
3 Correct 3 ms 16476 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16476 KB Output is correct
2 Correct 3 ms 16476 KB Output is correct
3 Correct 3 ms 16476 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16476 KB Output is correct
2 Correct 3 ms 16476 KB Output is correct
3 Correct 3 ms 16476 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16472 KB Output is correct
2 Correct 3 ms 16520 KB Output is correct
3 Correct 5 ms 16476 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16476 KB Output is correct
2 Correct 3 ms 16476 KB Output is correct
3 Correct 4 ms 16476 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16476 KB Output is correct
2 Correct 11 ms 16476 KB Output is correct
3 Correct 13 ms 16724 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 21084 KB Output is correct
2 Correct 118 ms 22648 KB Output is correct
3 Incorrect 153 ms 26992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2178 ms 81940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

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