oj.uz

Submission #94942

# Submission time Handle Problem Language Result Execution time Memory
94942 2019-01-25T11:52:49 Z JustInCase Zamjene (COCI16_zamjene) C++17
84 / 140
 1452 ms 67320 KB 
#include <bits/stdc++.h>

const int32_t BASE = 143;
const int32_t MOD = 1e9 + 7;

const int32_t MAX_N = 1e6;
const int32_t MAX_P = 1e6;

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

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

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

	totalWithDiff[diff] -= cnt;
}

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

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

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

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

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

		int32_t diffX = sumsP[parX] - sumsQ[parX];
		if(diffX < 0) {
			diffX += MOD;
		}
		Remove(diffX, sizes[parX]);
		
		int32_t diffY = sumsP[parY] - sumsQ[parY];
		if(diffY < 0) {
			diffY += MOD;
		}
		Remove(diffY, sizes[parY]);

		sumsP[parX] -= basePowers[p[x] - 1];
		if(sumsP[parX] < 0) {
			sumsP[parX] += MOD;
		}
		sumsP[parX] = ((int64_t) sumsP[parX] + basePowers[p[y] - 1]) % MOD;

		sumsP[parY] -= basePowers[p[y] - 1];
		if(sumsP[parY] < 0) {
			sumsP[parY] += MOD;
		}
		sumsP[parY] = ((int64_t) sumsP[parY] + basePowers[p[x] - 1]) % MOD;
		
		std::swap(p[x], p[y]);

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

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

		if(parX == parY) {
			return;
		}

		int32_t diffX = sumsP[parX] - sumsQ[parX];
		if(diffX < 0) {
			diffX += MOD;
		}
		Remove(diffX, sizes[parX]);
		
		int32_t diffY = sumsP[parY] - sumsQ[parY];
		if(diffY < 0) {
			diffY += MOD;
		}
		Remove(diffY, sizes[parY]);

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

UnionFind dsu;

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

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

	for(int32_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(int32_t i = 1; i < q[n]; i++) {
		basePowers[i] = ((int64_t) basePowers[i - 1] * BASE) % MOD;
	}
	
	dsu.Init(n);

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

		if(t == 1) {
			int32_t a, b;
			std::cin >> a >> b;
		
			dsu.Swap(a, b);
		}
		else if(t == 2) {
			int32_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 504 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 504 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 6 ms 888 KB Output is correct
3 Correct 6 ms 880 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4216 KB Output is correct
2 Correct 59 ms 5624 KB Output is correct
3 Incorrect 81 ms 7432 KB Output isn't correct

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 848 ms 41144 KB Output is correct
2 Incorrect 1452 ms 67320 KB Output isn't correct
3 Halted 0 ms 0 KB -