Submission #408674

#	Time	Username	Problem	Language	Result	Execution time	Memory
408674		RGBB	Duathlon (APIO18_duathlon)	C++14	100 / 100	263 ms	69708 KiB

count_triplets

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pp;
const int MAXN=2*1e5;
int n,m;
ll ans;
//biconnection stuffs
int t,cnt,low[MAXN],dist[MAXN],parent[MAXN];
bool vis[MAXN];
vector<int>adj[MAXN];
unordered_set<int>bcc[MAXN];
stack<pp>stk;
void dfs(int p){
    vis[p]=true;
    low[p]=t;
    dist[p]=t;
    t++;
    int children=0;
    for(int i:adj[p]){
        if(!vis[i]){
            children++;
            parent[i]=p;
            stk.push({p,i});
            dfs(i);
            low[p]=min(low[p],low[i]);
            if((dist[p]==0&&children>1)||(dist[p]>0&&low[i]>=dist[p])){
                while(true){
                    bcc[cnt].insert(stk.top().first);
                    bcc[cnt].insert(stk.top().second);
                    if(stk.top()==make_pair(p,i)){
                        stk.pop();
                        break;
                    }
                    stk.pop();
                }
                cnt++;
            }
        }
        else if(i!=parent[p]){
            low[p]=min(low[p],dist[i]);
            if(dist[i]<dist[p])stk.push({p,i});
        }
    }
}
unordered_set<int>art;
void dfs2(int p){
    vis[p]=true;
    dist[p]=t;
    low[p]=t;
    t++;
    int children=0;
    for(int i:adj[p]){
        if(i==parent[p])continue;
        if(vis[i])low[p]=min(low[p],dist[i]);
        else{
            parent[i]=p;
            dfs2(i);
            low[p]=min(low[p],low[i]);
            if(low[i]>=dist[p]&&parent[p]!=-1){
                art.insert(p);
                children++;
            }
        }
    }
    if(parent[p]==-1&&children>1)art.insert(p);
}
int num,si[MAXN],group[MAXN];
bool type[MAXN];
vector<int>edge[MAXN];
void construct(int p){
    vis[p]=true;
    queue<int>q;
    q.push(p);
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        for(auto&i:edge[cur]){
            if(vis[i])continue;
            parent[i]=cur;
            vis[i]=true;
            q.push(i);
        }
    }
}
vector<int>roots;
ll freq[MAXN][2],dp[MAXN];
ll below(int p){
    for(auto&i:edge[p])if(i!=parent[p])freq[p][0]+=below(i)+si[i];
    return freq[p][0];
}
void above(int p){
    for(auto&i:edge[p]){
        if(i==parent[p])continue;
        freq[i][1]=freq[p][1]+si[p]+freq[p][0]-freq[i][0]-si[i];
        above(i);
    }
}
void solve(){
    for(int i=0;i<num;i++){
        if(type[i]){
            for(int y:edge[i]){
                ll a;
                if(y!=parent[i])a=freq[y][0]+1;
                else a=freq[i][1];
                ans-=si[i]*a*(a-1);
                dp[i]+=a*(a-1);
            }
        }
    }
    for(int i=0;i<num;i++){
        if(!type[i]){
            for(int y:edge[i]){
                if(y!=parent[i])ans-=dp[y]-freq[y][1]*(freq[y][1]-1);
                else ans-=dp[y]-(freq[i][0]+si[i])*(freq[i][0]+si[i]-1);
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //input
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        adj[a-1].push_back(b-1);
        adj[b-1].push_back(a-1);
    }
    //biconnect
    t=0;
    cnt=0;
    memset(low,0,sizeof(low));
    memset(dist,0,sizeof(dist));
    memset(parent,-1,sizeof(parent));
    memset(vis,false,sizeof(vis));
    for(int i=0;i<n;i++)if(!vis[i])dfs(i);
    if(!stk.empty()){
        while(!stk.empty()){
            bcc[cnt].insert(stk.top().first);
            bcc[cnt].insert(stk.top().second);
            stk.pop();
        }
        cnt++;
    }
    //articulation points
    memset(vis,false,sizeof(vis));
    for(int i=0;i<n;i++){
        if(!vis[i]){
            t=0;
            parent[i]=-1;
            dfs2(i);
        }
    }
    memset(vis,false,sizeof(vis));
    for(int i=n-1;i>=0;i--){
        if(!vis[i]){
            t=0;
            parent[i]=-1;
            dfs2(i);
        }
    }
    //construct forest nodes
    num=0;
    memset(si,0,sizeof(si));
    for(auto&i:art){
        group[i]=num;
        type[num]=false;
        si[num]=1;
        num++;
    }
    for(int i=0;i<cnt;i++){
        type[num]=true;
        for(auto&y:bcc[i]){
            if(art.find(y)!=art.end()){
                edge[num].push_back(group[y]);
                edge[group[y]].push_back(num);
            }
            else si[num]++;
        }
        num++;
    }
    //find roots and construct trees
    memset(vis,false,sizeof(vis));
    memset(parent,-1,sizeof(parent));
    for(int i=0;i<num;i++){
        if(!vis[i]){
            roots.push_back(i);
            construct(i);
        }
    }
    //tree dp
    ans=0;
    memset(freq,0,sizeof(freq));
    memset(dp,0,sizeof(dp));
    for(int i:roots){
        below(i);
        above(i);
        ll a=freq[i][0]+si[i];
        ans+=a*(a-1)*(a-2);
    }
    solve();
    //output answer
    cout<<ans<<"\n";
}

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