oj.uz

Submission #94946

# Submission time Handle Problem Language Result Execution time Memory
94946 2019-01-25T11:57:47 Z JustInCase Zamjene (COCI16_zamjene) C++17
140 / 140
 2837 ms 143944 KB 
#include <bits/stdc++.h>

const int64_t BASE = 1234577;

const int64_t MAX_N = 1e6;
const int64_t MAX_P = 1e6;

int64_t p[MAX_N + 5], q[MAX_N + 5];
int64_t basePowers[MAX_P + 5];
std::unordered_map< int64_t, int64_t > totalWithDiff;
int64_t totalPairs;

void Add(int64_t diff, int64_t cnt) {
	if(diff != 0) {
		totalPairs += (int64_t) cnt * totalWithDiff[-diff];
	}
	
	totalWithDiff[diff] += cnt;
}

void Remove(int64_t diff, int64_t cnt) {
	if(diff != 0) {
		totalPairs -= (int64_t) cnt * totalWithDiff[-diff];
	}

	totalWithDiff[diff] -= cnt;
}

class UnionFind {
private:
	int64_t parents[MAX_N + 5], sizes[MAX_N + 5], sumsP[MAX_N + 5], sumsQ[MAX_N + 5];

public:
	void Init(int64_t pCntNodes) {
		for(int64_t i = 1; i <= pCntNodes; i++) {
			sumsP[i] = basePowers[p[i] - 1];
			sumsQ[i] = basePowers[q[i] - 1];
			parents[i] = i;
			sizes[i] = 1;
			
			int64_t diff = sumsP[i] - sumsQ[i];
			Add(diff, 1);
		}
	}

	int64_t Find(int64_t x) {
		if(x == parents[x]) {
			return x;
		}
		else {
			parents[x] = Find(parents[x]);
			return parents[x];
		}
	}

	void Swap(int64_t x, int64_t y) {
		int64_t parX = Find(x);
		int64_t parY = Find(y);

		if(parX == parY) {
			std::swap(p[x], p[y]);
			return;
		}

		int64_t diffX = sumsP[parX] - sumsQ[parX];
		Remove(diffX, sizes[parX]);
		
		int64_t diffY = sumsP[parY] - sumsQ[parY];
		Remove(diffY, sizes[parY]);

		sumsP[parX] -= basePowers[p[x] - 1];
		sumsP[parX] = sumsP[parX] + basePowers[p[y] - 1];

		sumsP[parY] -= basePowers[p[y] - 1];
		sumsP[parY] = sumsP[parY] + basePowers[p[x] - 1];
		
		std::swap(p[x], p[y]);

		diffX = sumsP[parX] - sumsQ[parX];
		Add(diffX, sizes[parX]);
		
		diffY = sumsP[parY] - sumsQ[parY];
		Add(diffY, sizes[parY]);
	}

	void Union(int64_t x, int64_t y) {
		int64_t parX = Find(x);
		int64_t parY = Find(y);

		if(parX == parY) {
			return;
		}

		int64_t diffX = sumsP[parX] - sumsQ[parX];
		Remove(diffX, sizes[parX]);
		
		int64_t diffY = sumsP[parY] - sumsQ[parY];
		Remove(diffY, sizes[parY]);

		if(sizes[parX] <= sizes[parY]) {
			parents[parX] = parY;
			sizes[parY] += sizes[parX];
			sumsP[parY] = sumsP[parY] + sumsP[parX];
			sumsQ[parY] = sumsQ[parY] + sumsQ[parX];
			
			diffY = sumsP[parY] - sumsQ[parY];
			Add(diffY, sizes[parY]);
		}
		else {
			parents[parY] = parX;
			sizes[parX] += sizes[parY];
			sumsP[parX] = sumsP[parX] + sumsP[parY];
			sumsQ[parX] = sumsQ[parX] + sumsQ[parY];
		
			diffX = sumsP[parX] - sumsQ[parX];
			Add(diffX, sizes[parX]);
		}
	}
};

UnionFind dsu;

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

	int64_t n, m;
	std::cin >> n >> m;

	for(int64_t i = 1; i <= n; i++) {
		std::cin >> p[i];
		q[i] = p[i];
	}

	std::sort(q + 1, q + 1 + n);

	basePowers[0] = 1;
	for(int64_t i = 1; i < q[n]; i++) {
		basePowers[i] = basePowers[i - 1] * BASE;
	}
	
	dsu.Init(n);

	for(int64_t i = 0; i < m; i++) {
		int64_t t;
		std::cin >> t;

		if(t == 1) {
			int64_t a, b;
			std::cin >> a >> b;
		
			dsu.Swap(a, b);
		}
		else if(t == 2) {
			int64_t a, b;
			std::cin >> a >> b;

			dsu.Union(a, b);
		}
		else if(t == 3) {
			std::cout << (totalWithDiff[0] == n ? "DA" : "NE") << '\n';
		}
		else {
			std::cout << totalPairs << '\n';
		}
	}
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1012 KB Output is correct
2 Correct 6 ms 1020 KB Output is correct
3 Correct 6 ms 1016 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6572 KB Output is correct
2 Correct 73 ms 7928 KB Output is correct
3 Correct 73 ms 9736 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 35716 KB Output is correct
2 Correct 2122 ms 93336 KB Output is correct
3 Correct 2837 ms 143944 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1387 ms 77344 KB Output is correct
2 Correct 2161 ms 111576 KB Output is correct
3 Correct 1373 ms 94440 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 54344 KB Output is correct
2 Correct 1470 ms 79832 KB Output is correct
3 Correct 1332 ms 94356 KB Output is correct