| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 46458 |
2018-04-21T01:19:32 Z |
sorry_Benq |
Pipes (CEOI15_pipes) |
C++17 |
|
1256 ms |
24836 KB |
/**
* 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 time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4708 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
4736 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
5632 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
5376 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
5508 KB |
Output is correct |
| 2 |
Incorrect |
97 ms |
5224 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
165 ms |
6648 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
288 ms |
9544 KB |
Output is correct |
| 2 |
Correct |
257 ms |
8696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
441 ms |
18888 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
696 ms |
20920 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
887 ms |
24704 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1088 ms |
24836 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1256 ms |
23696 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
