Submission #990603

#	Time	Username	Problem	Language	Result	Execution time	Memory
990603		grogu	Duathlon (APIO18_duathlon)	C++14	66 / 100	68 ms	31836 KiB

count_triplets

    // __builtin_popcount(x)
    // __builtin_popcountll(x)
    #define here cerr<<"===========================================\n"
    #include <bits/stdc++.h>
    #define ld double
    #define ll long long
    #define ull unsigned long long
    #define llinf 100000000000000000LL // 10^17
    #define iinf 2000000000 // 2*10^9
    #define pb push_back
    #define popb pop_back
    #define fi first
    #define sc second
    #define endl '\n'
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    #define pld pair<ld,ld>
    #define sz(a) int(a.size())
    #define all(a) a.begin(),a.end()
    #define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
    using namespace std;
     
    #define maxn 200005
    ll n,m;
    vector<ll> g[maxn];
    vector<ll> v[maxn];
    ll low[maxn];
    ll in[maxn];
    bool vis[maxn];
    ll siz[maxn];
    ll it = 1;
    ll cnt = 1;
    ll comp = 0;
    stack<ll> st;
    void dfs(ll u,ll par){
        comp++;
        in[u] = it++;
        low[u] = in[u];
        st.push(u);
        for(ll s : g[u]){
            if(s==par) continue;
            if(in[s]){
                low[u] = min(low[u],low[s]);
            }else{
                dfs(s,u);
                low[u] = min(low[u],low[s]);
                if(low[s]>=in[u]){
                    v[u].pb(n+cnt);
                    while(sz(st)){
                        ll to = st.top();
                        st.pop();
                        v[n+cnt].pb(to);
                        if(to==s) break;
                    }
                    cnt++;
                }
            }
        }
     
    }
    ll ans = 0;
    ll f3(ll x){
        return x*(x-1)*(x-2);
    }
    ll f2(ll x){
        return x*(x-1);
    }
    void dfs2(ll u){
        if(u<=n) siz[u] = 1;
        for(ll s : v[u]){
            dfs2(s);
            siz[u]+=siz[s];
            if(u>n) ans-=f2(siz[s])*sz(v[u]);
        }
        if(u>n) ans-=f2(comp-siz[u])*sz(v[u]);
    }
    int main(){
    	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
        cin >> n >> m;
        for(ll i = 1;i<=m;i++){
            ll x,y; cin >> x >> y;
            g[x].pb(y);
            g[y].pb(x);
        }
        for(ll i = 1;i<=n;i++){
            if(in[i]==0){
                comp = 0;
                dfs(i,i);
                ans+=f3(comp);
                dfs2(i);
            }
        }
        cout<<ans<<endl;
    	return 0;
    }
    /*
    4 3
    1 2
    2 3
    3 4
    out: 8
    */
    /*
    4 4
    1 2
    2 3
    3 4
    4 2
    out: 14
    */

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10