# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
496696 |
2021-12-21T22:19:20 Z |
aryan12 |
Pipes (CEOI15_pipes) |
C++17 |
|
1045 ms |
65536 KB |
#include <bits/stdc++.h>
using namespace std;
//#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 5;
int par[2][N];
vector<int> g[N];
int disc[N], low[N], tim = 0;
bool vis[N];
void dfs(int node, int parent) {
vis[node] = true;
disc[node] = ++tim;
low[node] = tim;
bool flag = false;
for(int i = 0; i < g[node].size(); i++) {
if(g[node][i] == parent && !flag) {
flag = true;
continue;
}
if(vis[g[node][i]]) {
low[node] = min(low[node], disc[g[node][i]]);
}
else {
dfs(g[node][i], node);
low[node] = min(low[node], low[g[node][i]]);
if(low[g[node][i]] > disc[node]) {
cout << node << " " << g[node][i] << "\n";
}
}
}
}
int Find(int x, int d) {
if(par[d][x] == x) {
return x;
}
return par[d][x] = Find(par[d][x], d);
}
void Unite(int u, int v, int d) {
v = Find(v, d), u = Find(u, d);
par[d][v] = u;
}
void Solve() {
int n, m;
cin >> n >> m;
for(int i = 0; i <= n; i++) {
par[0][i] = i;
par[1][i] = i;
}
for(int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
if(Find(u, 0) != Find(v, 0)) {
Unite(u, v, 0);
g[u].push_back(v);
g[v].push_back(u);
}
else if(Find(u, 1) != Find(v, 1)) {
Unite(u, v, 1);
g[u].push_back(v);
g[v].push_back(u);
}
}
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
dfs(i, -1);
}
}
}
int32_t main() {
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) {
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Compilation message
pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i = 0; i < g[node].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2768 KB |
Output is correct |
2 |
Correct |
1 ms |
2684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3280 KB |
Output is correct |
2 |
Correct |
4 ms |
3080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
8452 KB |
Output is correct |
2 |
Correct |
98 ms |
8196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
142 ms |
13532 KB |
Output is correct |
2 |
Correct |
179 ms |
14636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
277 ms |
21464 KB |
Memory limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
378 ms |
31344 KB |
Memory limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
578 ms |
45128 KB |
Memory limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
699 ms |
58012 KB |
Memory limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
843 ms |
65536 KB |
Memory limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1045 ms |
65536 KB |
Memory limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |