Submission #743332

#	Time	Username	Problem	Language	Result	Execution time	Memory
743332		alvingogo	Duathlon (APIO18_duathlon)	C++14	31 / 100	119 ms	48084 KiB

count_triplets

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

/*
1. tarjan find BCC(vertex)

2. block-cut tree
type, size, subtree size

3. dp
we iterate c
square -> s, t aren't in the same subtree -> add to all the circle connecting to the square
circle -> s, t aren't in the same subtree


done?
*/

vector<vector<int> > e,bcc; 
vector<int> low,dfn,cv;
int cnt=0,cc=0,cr=0;
stack<int> st;
void tj(int r,int f){
    int sl=0;
    cnt++;
    dfn[r]=low[r]=cnt;
    st.push(r);
    for(auto h:e[r]){
        if(h!=f){
            if(!dfn[h]){
                tj(h,r);
                sl++;
                low[r]=min(low[r],low[h]);
                if(low[h]>=dfn[r]){
                    if(f!=-1){
                        if(!cv[r]){
                            cr++;
                            cv[r]=cr;
                        }
                    }
                    bcc.push_back(vector<int>());
                    while(st.top()!=r){
                        bcc[cc].push_back(st.top());
                        st.pop();
                    }
                    bcc[cc].push_back(st.top());
                    cc++;
                }
            }
            else{
                low[r]=min(low[r],dfn[h]);
            }
        }
    }
    if(f==-1 && sl>=2){
        if(!cv[r]){
            cr++;
            cv[r]=cr;
        }
    }
    if(f==-1){
        st.pop();
    }
}

struct no{
    vector<int> ch;
    int t=0,sq=0;
    long long tp=0;
    int sz=1;
    int vis=0;
};
vector<no> v;
long long ans=0;
int dfs3(int r,int f){
    v[r].vis=1;
    if(v[r].t){
        v[r].sz=v[r].sq;
    }
    int k=v[r].sz;
    for(auto h:v[r].ch){
        if(h!=f){
            k+=dfs3(h,r);
        }
    }
    return k;
}
void dfs(int r,int f,int n){
    for(auto h:v[r].ch){
        if(h!=f){
            dfs(h,r,n);
            v[r].sz+=v[h].sz;
            if(v[r].t){
                v[r].tp+=1ll*v[h].sz*(v[h].sz-1);
            }
        }
    }
    if(v[r].t){
        v[r].tp+=1ll*(n-v[r].sz)*(n-v[r].sz-1);
        ans-=1ll*v[r].sq*v[r].tp;
    }
}
void dfs2(int r,int f,int n){
    for(auto h:v[r].ch){
        if(h!=f){
            dfs2(h,r,n);
            if(!v[r].t){
                ans-=(v[h].tp-1ll*(n-v[h].sz)*(n-v[h].sz-1));
            }
        }
    }
    if(!v[r].t){
        ans-=(v[f].tp-1ll*(v[r].sz)*(v[r].sz-1));
    }
}
signed main(){
    AquA;
    int n;
    cin >> n;
    if(n<3){
        cout << 0 << "\n";
        return 0;
    }
    int m;
    cin >> m;
    e.resize(n);
    low.resize(n);
    dfn.resize(n);
    cv.resize(n);
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for(int i=0;i<n;i++){
        if(!dfn[i]){
            tj(i,-1);
        }
    }
    int s=cc;
    for(int i=0;i<n;i++){
        if(cv[i]){
            s++;
        }
    }
    v.resize(s);
    for(int i=0;i<cc;i++){
        v[i].t=1;
        for(auto h:bcc[i]){
            if(cv[h]){
                v[i].ch.push_back(cv[h]+cc-1);
                v[cv[h]+cc-1].ch.push_back(i);
            }
            else{
                v[i].sq++;
            }
        }
    }
    for(int i=0;i<cc;i++){
        if(!v[i].vis){
            int k=dfs3(i,i);
            ans+=1ll*k*(k-1)*(k-2);
            dfs(i,i,k);
            dfs2(i,i,k);
        }
    }
    
    cout << ans << "\n";
    return 0;
}

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