# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
95118 |
2019-01-27T12:44:05 Z |
MrTEK |
Pipes (CEOI15_pipes) |
C++14 |
|
1223 ms |
13360 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> ii;
const int N = 1e5 + 5;
int n,m,u,v,t,tin[N],fup[N];
vector <int> ed[N];
bool vis[N];
class dsu { public:
int dad[N];
void init() {
for (int i = 1 ; i <= n ; i++)
dad[i] = i;
}
int find(int x) {
if (x == dad[x])
return x;
return dad[x] = find(dad[x]);
}
bool merge(int x,int y) {
int dx = find(x) , dy = find(y);
if (dx == dy)
return false;
dad[dx] = dy;
return true;
}
}t1,t2;
void is_bridge(int x,int y) {
int l = lower_bound(ed[x].begin(),ed[x].end(),y) - ed[x].begin();
int r = upper_bound(ed[x].begin(),ed[x].end(),y) - ed[x].begin();
if (r != l + 1)
return;
cout << x << " " << y << endl;
}
void dfs(int cur,int par) {
vis[cur] = true;
tin[cur] = fup[cur] = ++t;
for (auto i : ed[cur]) {
if (i == par)
continue;
if (vis[i])
fup[cur] = min(fup[cur],tin[i]);
else{
dfs(i,cur);
fup[cur] = min(fup[cur],fup[i]);
if (fup[i] > tin[cur])
is_bridge(cur,i);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
t1.init();
t2.init();
for (int i = 1 ; i <= m ; i++) {
cin >> u >> v;
if (t1.merge(u,v) || t2.merge(u,v)) {
ed[u].push_back(v);
ed[v].push_back(u);
}
}
for (int i = 1 ; i <= n ; i++)
sort(ed[i].begin(),ed[i].end());
for (int i = 1 ; i <= n ; i++)
if (vis[i] == false)
dfs(i,-1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2688 KB |
Output is correct |
2 |
Correct |
4 ms |
2688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
3200 KB |
Output is correct |
2 |
Correct |
9 ms |
3072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
3052 KB |
Output is correct |
2 |
Correct |
96 ms |
2944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
159 ms |
3704 KB |
Output is correct |
2 |
Correct |
191 ms |
3324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
299 ms |
5176 KB |
Output is correct |
2 |
Correct |
251 ms |
5124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
415 ms |
10232 KB |
Output is correct |
2 |
Correct |
364 ms |
7160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
626 ms |
11228 KB |
Output is correct |
2 |
Correct |
583 ms |
8892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
942 ms |
13344 KB |
Output is correct |
2 |
Correct |
879 ms |
9092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1128 ms |
13360 KB |
Output is correct |
2 |
Correct |
1070 ms |
9080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1223 ms |
12776 KB |
Output is correct |
2 |
Correct |
1136 ms |
10312 KB |
Output is correct |