#include "sabotaz.h" #include "message.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 200 * 1000; int N, M, in[MAXN], low[MAXN], dfstime, bridges; vector<pair<int, int>> graph[MAXN]; vector<pair<int, int>> edges; void visit(int u, int parent) { low[u] = in[u] = dfstime++; for (auto edge : graph[u]) { int v, edge_id; tie(v, edge_id) = edge; if (edge_id == parent) continue; if (in[v] == -1) { edges.emplace_back(v, u); visit(v, edge_id); if (low[v] == in[v]) ++bridges; low[u] = min(low[u], low[v]); } else { low[u] = min(low[u], in[v]); } } for (auto edge : graph[u]) { int v = edge.first; if (in[v] == low[u]) { edges.emplace_back(u, v); break; } } } void DFS() { for (int i = 0; i < edges.size(); ++i) { graph[edges[i].first].emplace_back(edges[i].second, i); graph[edges[i].second].emplace_back(edges[i].first, i); } edges.clear(); for (int i = 0; i < N; ++i) in[i] = low[i] = -1; dfstime = 0; bridges = 0; for (int i = 0; i < N; ++i) if (in[i] == -1) visit(i, -1); for (int i = 0; i < N; ++i) { vector<pair<int, int>> temp; graph[i].swap(temp); } } const int MESSAGES = 20; int main() { N = NumberOfIsles(); M = NumberOfBridges(); int from = MyNodeId() * (long long)M / NumberOfNodes(); int to = (1 + MyNodeId()) * (long long)M / NumberOfNodes(); for (int i = from; i < to; ++i) edges.emplace_back(BridgeEndA(i), BridgeEndB(i)); int rounds = 1; while ((1 << (rounds - 1)) < NumberOfNodes()) ++rounds; for (int round = 0; round < rounds; ++round) { if ((MyNodeId() & ((1 << round) - 1)) == 0) { // cerr << MyNodeId() << " works in round " << round << " "; DFS(); if ((MyNodeId() >> round) & 1) { int target = MyNodeId() - (1 << round); // cerr << " and sends to " << target << endl; for (int message = 0; message < MESSAGES; ++message) { for (int i = message; i < edges.size(); i += MESSAGES) { PutInt(target, edges[i].first); PutInt(target, edges[i].second); } PutInt(target, -1); PutInt(target, -1); Send(target); } } else if (MyNodeId() + (1 << round) < NumberOfNodes()) { int source = MyNodeId() + (1 << round); // cerr << " and receives from " << source << endl; for (int message = 0; message < MESSAGES; ++message) { Receive(source); while (true) { int a = GetInt(source); int b = GetInt(source); if (a == -1 && b == -1) break; edges.emplace_back(a, b); } } } } } if (MyNodeId() == 0) { cout << bridges << endl; } return 0; }
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 | #include "sabotaz.h" #include "message.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 200 * 1000; int N, M, in[MAXN], low[MAXN], dfstime, bridges; vector<pair<int, int>> graph[MAXN]; vector<pair<int, int>> edges; void visit(int u, int parent) { low[u] = in[u] = dfstime++; for (auto edge : graph[u]) { int v, edge_id; tie(v, edge_id) = edge; if (edge_id == parent) continue; if (in[v] == -1) { edges.emplace_back(v, u); visit(v, edge_id); if (low[v] == in[v]) ++bridges; low[u] = min(low[u], low[v]); } else { low[u] = min(low[u], in[v]); } } for (auto edge : graph[u]) { int v = edge.first; if (in[v] == low[u]) { edges.emplace_back(u, v); break; } } } void DFS() { for (int i = 0; i < edges.size(); ++i) { graph[edges[i].first].emplace_back(edges[i].second, i); graph[edges[i].second].emplace_back(edges[i].first, i); } edges.clear(); for (int i = 0; i < N; ++i) in[i] = low[i] = -1; dfstime = 0; bridges = 0; for (int i = 0; i < N; ++i) if (in[i] == -1) visit(i, -1); for (int i = 0; i < N; ++i) { vector<pair<int, int>> temp; graph[i].swap(temp); } } const int MESSAGES = 20; int main() { N = NumberOfIsles(); M = NumberOfBridges(); int from = MyNodeId() * (long long)M / NumberOfNodes(); int to = (1 + MyNodeId()) * (long long)M / NumberOfNodes(); for (int i = from; i < to; ++i) edges.emplace_back(BridgeEndA(i), BridgeEndB(i)); int rounds = 1; while ((1 << (rounds - 1)) < NumberOfNodes()) ++rounds; for (int round = 0; round < rounds; ++round) { if ((MyNodeId() & ((1 << round) - 1)) == 0) { // cerr << MyNodeId() << " works in round " << round << " "; DFS(); if ((MyNodeId() >> round) & 1) { int target = MyNodeId() - (1 << round); // cerr << " and sends to " << target << endl; for (int message = 0; message < MESSAGES; ++message) { for (int i = message; i < edges.size(); i += MESSAGES) { PutInt(target, edges[i].first); PutInt(target, edges[i].second); } PutInt(target, -1); PutInt(target, -1); Send(target); } } else if (MyNodeId() + (1 << round) < NumberOfNodes()) { int source = MyNodeId() + (1 << round); // cerr << " and receives from " << source << endl; for (int message = 0; message < MESSAGES; ++message) { Receive(source); while (true) { int a = GetInt(source); int b = GetInt(source); if (a == -1 && b == -1) break; edges.emplace_back(a, b); } } } } } if (MyNodeId() == 0) { cout << bridges << endl; } return 0; } |