/** Created by: Humberto Yusta
Codeforces User: humbertoyusta
Country: Cuba
Copyright�� */
#include<bits/stdc++.h>
using namespace std;
/// Pragmas:
//#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2") //Enable AVX
/// Macros:
//#define int long long
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
#define enl '\n'
typedef pair<int,int> ii;
typedef long double ld;
typedef unsigned long long ull;
/// Constraints:
const int maxn = 100010;
const int mod = 1000000007;
const ld eps = 1e-9;
const int inf = ((1ll<<31ll)-1ll);
const int INF = 2000000000000000000ll;
const ld pi = acos(-1);
/// Prime Numbers:
// 2, 173, 179, 181, 197, 311, 331, 737, 1009, 2011, 2027, 3079, 4001, 10037, 10079, 20011, 20089;
// 100003, 100019, 100043, 200003, 200017, 1000003, 1000033, 1000037, 1000081;
// 2000003, 2000029, 2000039, 1000000007, 1000000021, 2000000099;
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lgx(x,b) ( log(x) / log(b) )
/// Red-Black Tree Template ---------------------------------
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long , null_type , less<long long> , rb_tree_tag , tree_order_statistics_node_update > ordered_set;
/// Quick Pow------------------------------------------------
int qpow(int b,int e){
if( !e ) return 1;
if( e & 1 ) return qpow(b,e-1) * b % mod;
int pwur = qpow(b,e>>1);
return pwur * pwur % mod;
}
int modinv(int x){
return qpow(x,mod-2);
}
/// My Code -------------------------------------------------
int n, m, lca[maxn][17], p[maxn], ran[maxn], lv[maxn], ac[maxn], ans[maxn], mk[maxn], aa, bb;
vector<int> g[maxn];
set<ii> s;
int find_(int x){
if( p[x] == x ) return x;
return p[x] = find_(p[x]);
}
void dfs(int u,int p){
for(int i=1; i<=16; i++){
lca[u][i] = lca[lca[u][i-1]][i-1];
if( lca[u][i] == 0 ) break;
}
for( auto v : g[u] ){
if( v != p ){
lv[v] = lv[u] + 1;
lca[v][0] = u;
dfs(v,u);
}
}
}
void dfs_ac(int u,int p,int flag){
for( auto v : g[u] ){
if( v == p || v == flag ) continue;
dfs_ac(v,u,flag);
ac[u] += ac[v];
//ac[u] = 0;
}
//db(u)db(p)db(ac[u])
if( ac[u] > 0 ){
//db(u)db(p)db("1")
s.insert({u,p});
s.insert({p,u});
}
}
void dfs_cl(int u,int p,int flag){
ac[u] = 0;
for( auto v : g[u] ){
if( v == p || v == flag ) continue;
dfs_cl(v,u,flag);
}
}
void dfs_ac2(int u,int p,int flag){
mk[u] = 1;
for( auto v : g[u] ){
if( v == p || v == flag ) continue;
dfs_ac2(v,u,flag);
ac[u] += ac[v];
//db(u)db(ac[u])
//ac[u] = 0;
}
//db(u)
//db(ac[u])
if( ac[u] > 0 ){
//db(u)db(p)db("2")
s.insert({u,p});
s.insert({p,u});
}
}
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cout.setf(ios::fixed); cout.precision(0);
srand(time(NULL));
//freopen("a.in","r",stdin);
//freopen("a.in","w",stdout);
cin >> n >> m;
for(int i=1; i<=n; i++){
p[i] = i;
ran[i] = 1;
}
int u, v, LCA;
for(int i=1; i<=m; i++){
cin >> u >> v;
aa = u;
bb = v;
while( p[aa] != aa ){ p[aa] = p[p[aa]]; aa = p[aa]; }
while( p[bb] != bb ){ p[bb] = p[p[bb]]; bb = p[bb]; }
if( aa == bb ){
ac[u]++;
ac[v]++;
if( lv[u] < lv[v] )
swap( u , v );
for(int i=lg2(lv[u]); i>=0; i--)
if( lv[u] - ( 1 << i ) >= lv[v] && lca[u][i] )
u = lca[u][i];
if( u == v ) LCA = u;
else{
for(int i=lg2(lv[u]); i>=0; i--)
if( lca[u][i] != lca[v][i] && ( lca[u][i] && lca[v][i] ) )
u = lca[u][i], v = lca[v][i];
LCA = lca[u][0];
}
ac[LCA] -= 2;
//db(u)db(v)db(query(u,v))
}
else{
if( ran[aa] < ran[bb] ){
swap( aa , bb );
swap( u , v );
}
dfs_ac(find_(v),find_(v),u);
dfs_cl(find_(v),find_(v),u);
lv[v] = lv[u] + 1;
lca[v][0] = u;
dfs(v,u);
g[v].pb(u);
g[u].pb(v);
p[bb] = aa;
ran[aa] += ran[bb];
}
}
for(int i=1; i<=n; i++){
if( !mk[find_(i)] ){
dfs_ac2(find_(i),find_(i),0);
}
}
s.insert({mod,mod});
for(int i=1; i<=n; i++){
for(auto j : g[i]){
if( *s.lower_bound({i,j}) != (ii){i,j} ){
cout << i << ' ' << j << '\n';
s.insert({j,i});
}
}
}
return 0;
}
Compilation message
pipes.cpp:30:17: warning: overflow in implicit constant conversion [-Woverflow]
const int INF = 2000000000000000000ll;
^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
3712 KB |
Output is correct |
| 2 |
Correct |
10 ms |
3712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
189 ms |
8952 KB |
Output is correct |
| 2 |
Correct |
166 ms |
8824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
336 ms |
14588 KB |
Output is correct |
| 2 |
Correct |
377 ms |
16120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
581 ms |
23960 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
977 ms |
38264 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1628 ms |
52856 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2229 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2660 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3432 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
