#include "dzialka.h" #include "message.h" #include <bits/stdc++.h> using namespace std; const int MAX = 75005; int h[MAX], p[MAX], sz[MAX], vis[MAX]; int N, ID, n, m; /* ----------------------------------- CZESC 1 ----- */ void fun1() { int k = m / N + 1; int k2 = n / N + 1; int pocz = ID * k, konc = (ID + 1) * k - 1; konc = min(konc, m-1); if (pocz >= m) return; for (int i = 0; i < n; i++) { for (int j = pocz; j <= konc; j++) { h[j]++; if (!IsUsableCell(i, j)) h[j] = 0; } if (i % k2 == 0) { int ID2 = i / k2; for (int j = pocz; j <= konc; j++) PutInt(ID2, h[j]); Send(ID2); } } } /* ----------------------------------- CZESC 2 ----- */ int Find(int x) { if (p[x] == x) return x; return p[x] = Find(p[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a != b) sz[a] += sz[b]; p[b] = a; } unsigned long long fun2() { int k = n / N + 1; int k2 = m / N + 1; int pocz = ID * k, konc = (ID + 1) * k - 1; konc = min(konc, n-1); if (pocz >= n) return 0; for (int j = 0; j < m; j++) if (j % k2 == 0) { int ID2 = j / k2; Receive(ID2); for (int j2 = j; j2 < min(j + k2, m); j2++) h[j2] = GetInt(ID2); } unsigned long long result = 0; for (int i = pocz; i <= konc; i++) { if (i != pocz) { for (int j = 0; j < m; j++) { h[j]++; if (!IsUsableCell(i, j)) h[j] = 0; } } vector<pair<int,int>> pos; p[0] = 0; sz[0] = 0; p[m+1] = m+1; sz[m+1] = 0; for (int j = 0; j < m; j++) { p[j+1] = j+1; sz[j+1] = 1; vis[j+1] = 0; pos.push_back({h[j], j+1}); } sort(pos.begin(), pos.end()); reverse(pos.begin(), pos.end()); for (auto pp: pos) { vis[pp.second] = 1; int sz1 = 0; if (vis[pp.second-1]) sz1 = sz[Find(pp.second-1)]; int sz2 = 0; if (vis[pp.second+1]) sz2 = sz[Find(pp.second+1)]; result += 1LL * (sz1+1) * (sz2+1) * pp.first; if (vis[pp.second-1]) Union(pp.second, pp.second-1); if (vis[pp.second+1]) Union(pp.second, pp.second+1); } } return result; } int main() { N = NumberOfNodes(); ID = MyNodeId(); n = GetFieldHeight(); m = GetFieldWidth(); fun1(); long long result = fun2(); if (ID != 0) { PutLL(0, result); Send(0); } else { unsigned long long elo = result; for (int i = 1; i < N; i++) { Receive(i); elo += GetLL(i); } std::cout << elo << "\n"; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | #include "dzialka.h" #include "message.h" #include <bits/stdc++.h> using namespace std; const int MAX = 75005; int h[MAX], p[MAX], sz[MAX], vis[MAX]; int N, ID, n, m; /* ----------------------------------- CZESC 1 ----- */ void fun1() { int k = m / N + 1; int k2 = n / N + 1; int pocz = ID * k, konc = (ID + 1) * k - 1; konc = min(konc, m-1); if (pocz >= m) return; for (int i = 0; i < n; i++) { for (int j = pocz; j <= konc; j++) { h[j]++; if (!IsUsableCell(i, j)) h[j] = 0; } if (i % k2 == 0) { int ID2 = i / k2; for (int j = pocz; j <= konc; j++) PutInt(ID2, h[j]); Send(ID2); } } } /* ----------------------------------- CZESC 2 ----- */ int Find(int x) { if (p[x] == x) return x; return p[x] = Find(p[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a != b) sz[a] += sz[b]; p[b] = a; } unsigned long long fun2() { int k = n / N + 1; int k2 = m / N + 1; int pocz = ID * k, konc = (ID + 1) * k - 1; konc = min(konc, n-1); if (pocz >= n) return 0; for (int j = 0; j < m; j++) if (j % k2 == 0) { int ID2 = j / k2; Receive(ID2); for (int j2 = j; j2 < min(j + k2, m); j2++) h[j2] = GetInt(ID2); } unsigned long long result = 0; for (int i = pocz; i <= konc; i++) { if (i != pocz) { for (int j = 0; j < m; j++) { h[j]++; if (!IsUsableCell(i, j)) h[j] = 0; } } vector<pair<int,int>> pos; p[0] = 0; sz[0] = 0; p[m+1] = m+1; sz[m+1] = 0; for (int j = 0; j < m; j++) { p[j+1] = j+1; sz[j+1] = 1; vis[j+1] = 0; pos.push_back({h[j], j+1}); } sort(pos.begin(), pos.end()); reverse(pos.begin(), pos.end()); for (auto pp: pos) { vis[pp.second] = 1; int sz1 = 0; if (vis[pp.second-1]) sz1 = sz[Find(pp.second-1)]; int sz2 = 0; if (vis[pp.second+1]) sz2 = sz[Find(pp.second+1)]; result += 1LL * (sz1+1) * (sz2+1) * pp.first; if (vis[pp.second-1]) Union(pp.second, pp.second-1); if (vis[pp.second+1]) Union(pp.second, pp.second+1); } } return result; } int main() { N = NumberOfNodes(); ID = MyNodeId(); n = GetFieldHeight(); m = GetFieldWidth(); fun1(); long long result = fun2(); if (ID != 0) { PutLL(0, result); Send(0); } else { unsigned long long elo = result; for (int i = 1; i < N; i++) { Receive(i); elo += GetLL(i); } std::cout << elo << "\n"; } } |