Submission #249975

#	Time	Username	Problem	Language	Result	Execution time	Memory
249975		humbertoyusta	Pipes (CEOI15_pipes)	C++14	40 / 100	3432 ms	65536 KiB

pipes

    /**   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 (stderr)

pipes.cpp:30:17: warning: overflow in implicit constant conversion [-Woverflow]
 const int INF = 2000000000000000000ll;
                 ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10