Submission #46458

#TimeUsernameProblemLanguageResultExecution timeMemory
46458sorry_BenqPipes (CEOI15_pipes)C++17
10 / 100
1256 ms24836 KiB
/** * Sources: various */ #pragma GCC optimize("O3") #pragma GCC target("sse4") #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #define NIL -1 using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pii; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; template<typename T> ostream& operator<< (ostream& out, const pair<T, T>& v) { out << "{" << v.first << ", " << v.second << "}"; return out; } template<typename T> ostream& operator<< (ostream& out, const vector<T>& v) { out << "["; size_t last = v.size() - 1; for(size_t i = 0; i < v.size(); ++i) { out << v[i]; if (i != last) out << ", "; } out << "]"; return out; } template<typename T> ostream& operator<< (ostream& out, const set<T>& v) { out << "["; auto pen = v.end(); pen--; for (auto it = v.begin(); it != v.end(); it++){ out << *it; if (it != pen){ out << ", "; } } out << "]"; return out; } template<typename T> ostream& operator<< (ostream& out, const Tree<T>& v) { out << "["; auto pen = v.end(); pen--; for (auto it = v.begin(); it != v.end(); it++){ out << *it; if (it != pen){ out << ", "; } } out << "]"; return out; } template<int SZ> struct DSU { int par[SZ]; DSU() { F0R(i,SZ) par[i] = i; } int get(int x) { // path compression if (par[x] != x) par[x] = get(par[x]); return par[x]; } bool unite(int x, int y) { // union-by-rank x = get(x), y = get(y); if (x == y) return 0; par[y] = x; return 1; } }; class Graph { int V; // No. of vertices list<int> *adj; // A dynamic array of adjacency lists void bridgeUtil(int v, bool visited[], int disc[], int low[], int parent[]); public: Graph(int V); // Constructor void addEdge(int v, int w); // to add an edge to graph void bridge(); // prints all bridges }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); // Note: the graph is undirected } // A recursive function that finds and prints bridges using // DFS traversal // u --> The vertex to be visited next // visited[] --> keeps tract of visited vertices // disc[] --> Stores discovery times of visited vertices // parent[] --> Stores parent vertices in DFS tree void Graph::bridgeUtil(int u, bool visited[], int disc[], int low[], int parent[]) { // A static variable is used for simplicity, we can // avoid use of static variable by passing a pointer. static int time = 0; // Mark the current node as visited visited[u] = true; // Initialize discovery time and low value disc[u] = low[u] = ++time; // Go through all vertices aadjacent to this list<int>::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { int v = *i; // v is current adjacent of u // If v is not visited yet, then recur for it if (!visited[v]) { parent[v] = u; bridgeUtil(v, visited, disc, low, parent); // Check if the subtree rooted with v has a // connection to one of the ancestors of u low[u] = min(low[u], low[v]); // If the lowest vertex reachable from subtree // under v is below u in DFS tree, then u-v // is a bridge if (low[v] > disc[u]) cout << u + 1 <<" " << v + 1 << endl; } // Update low value of u for parent function calls. else if (v != parent[u]) low[u] = min(low[u], disc[v]); } } // DFS based function to find all bridges. It uses recursive // function bridgeUtil() void Graph::bridge() { // Mark all the vertices as not visited bool *visited = new bool[V]; int *disc = new int[V]; int *low = new int[V]; int *parent = new int[V]; // Initialize parent and visited arrays for (int i = 0; i < V; i++) { parent[i] = NIL; visited[i] = false; } // Call the recursive helper function to find Bridges // in DFS tree rooted with vertex 'i' for (int i = 0; i < V; i++) if (visited[i] == false) bridgeUtil(i, visited, disc, low, parent); } Graph g(100005); DSU<100005> one_connected; DSU<100005> two_connected; int main() { ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin >> n >> m; int u, v; for (int i = 0; i < m; i++){ cin >> u >> v; u--; v--; if (!one_connected.unite(u, v)){ if (!two_connected.unite(u, v)){ continue; } else{ g.addEdge(u, v); } } else{ g.addEdge(u, v); } } g.bridge(); return 0; } // read!read!read!read!read!read!read! // ll vs. int!
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...