Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <map>
- using namespace std;
- typedef long long ll;
- const int maxn = 1e6 + 10;
- int dist(int si, int sj, int ei, int ej) {
- return abs(si - ei) + abs(sj - ej);
- }
- pair<int, int> idx[maxn];
- vector<pair<int, int>> graph[maxn];
- ll pref_sum[maxn];
- ll pref_sum2[maxn];
- int main() {
- ios_base::sync_with_stdio(false);
- int r, c;
- cin >> r >> c;
- vector<vector<int>> mat(r, vector<int>(c));
- int cnt = 1;
- for(int i = 0; i < r; i++) {
- for(int j = 0; j < c; j++) {
- cin >> mat[i][j];
- idx[cnt] = {i, j};
- cnt++;
- }
- }
- cnt = 1;
- for(int i = 0; i < r; i++) {
- for(int j = 0; j < c; j++) {
- int a = mat[i][j];
- int b = mat[idx[a].first][idx[a].second];
- int c = dist(i, j, idx[a].first, idx[a].second);
- graph[a].push_back(make_pair(b, c));
- cnt++;
- }
- }
- int n = r * c;
- vector<bool> visited(n + 1, false);
- for(int i = 1; i <= n; i++) {
- if(!visited[i]) {
- queue<int> q;
- q.push(i);
- vector<int> tmp;
- tmp.push_back(i);
- while(!q.empty()) {
- int c = q.front();
- q.pop();
- for(int i = 0; i < (int) graph[c].size(); i++) {
- int neighbour = graph[c][i].first, weight = graph[c][i].second;
- if(!visited[neighbour]) {
- visited[neighbour] = true;
- q.push(neighbour);
- tmp.push_back(weight);
- tmp.push_back(neighbour);
- }
- }
- }
- ll sum = 0;
- for(int i = 0; i < (int) tmp.size(); i++) {
- if(i % 2 == 1) {
- sum += tmp[i];
- cout << "|" << tmp[i] << "| ";
- }
- else {
- cout << tmp[i] << " ";
- if(i > 0) {
- pref_sum[tmp[i]] = sum - tmp[i - 1];
- }
- else {
- pref_sum[tmp[i]] = sum;
- }
- }
- }
- for(int i = 0; i < (int) tmp.size(); i++) {
- if(i % 2 == 1) {
- sum += tmp[i];
- cout << "|" << tmp[i] << "| ";
- }
- else {
- cout << tmp[i] << " ";
- pref_sum2[tmp[i]] = sum;
- }
- }
- cout << endl;
- }
- }
- cnt = 1;
- ll res = 0;
- for(int i = 0; i < r; i++) {
- for(int j = 0; j < c; j++) {
- if(cnt != mat[i][j]) {
- res += pref_sum2[cnt] - pref_sum[mat[i][j]];
- }
- }
- }
- cout << res << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
