oj.uz

Submission #861208

# Submission time Handle Problem Language Result Execution time Memory
861208 2023-10-15T16:32:30 Z beaboss Zamjene (COCI16_zamjene) C++14
0 / 140
 1146 ms 36064 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<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.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 21080 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 21084 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 21084 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 21080 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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