Submission #1132766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132766		boyliguanhan	Duathlon (APIO18_duathlon)	C++17	100 / 100	299 ms	85900 KiB

count_triplets

#include<bits/stdc++.h>
#define MULTICASE
#define int long long
using namespace std;
#define N 1<<19
vector<int>adj1[N],adj2[N];
int vis[N],SSZ,C,limit,id[N],dep[N],in[N],low[N],par[N],sz[N],C2;
set<pair<int,int>>st[N];
long long res,ans[N];
struct dsu{
    int par[N];
    int abp(int n){
        return par[n]==n?n:par[n]=abp(par[n]);
    }
    void init(){
        iota(par,par+(N),0);
    }
    void merge(int a,int b){
        par[abp(a)]=abp(b);
    }
} cycles;
void dfs1(int n,int p){
    SSZ++;
    low[n]=id[n]=++C2;
    for(auto i:adj1[n]){
        if(i==p)continue;
        if(!id[i]){
            dep[i]=dep[n]+1;dfs1(i,n);
            low[n]=min(low[n],low[i]);
            if(low[i]>id[n])
                adj2[n].push_back(i);
        } else if(dep[i]<dep[n])
            st[n].insert({dep[i],++C}),
            low[n]=min(low[n],low[i]);
    }
}
void dfsC(int n){
    for(auto i:adj1[n]){
        if(dep[i]-dep[n]-1)
            continue;
        dfsC(i);
        if(st[i].size()&&st[i].begin()->first<dep[n]){
            if(st[n].size()) cycles.merge(st[i].begin()
                        ->second,st[n].begin()->second);
            st[n].insert(*st[i].begin());
        }
    }
    if(st[n].size())
        in[n]=st[n].begin()->second;
}
void dfs2(int n,int p){
    for(auto i:adj1[n])
        if(dep[i]==dep[n]+1)
            dfs2(i,n);
    adj2[cycles.abp(in[n])].push_back(n);
    par[cycles.abp(in[n])]=p;
}
void dfs3(int n){
    long long sum=0,x;
    for(auto i:adj2[n]){
        dfs3(i);
        sum+=sz[n]*sz[i];
        sz[n]+=sz[i];
    }
    x=sz[n];
    sz[n]+=n<=limit;
    sum+=(SSZ-sz[n])*x;
    res+=(n>limit?adj2[n].size()-1:1)*sum*2;
}
signed main(){
    int n,m;
    cin>>n>>m; limit=C=n;
    for(int i=0;i<m;i++){
        int a,b; cin>>a>>b;
        adj1[a].push_back(b);
        adj1[b].push_back(a);
    }
    cycles.init();
    for(int i=1;i<=n;i++){
        if(!id[i]){
            SSZ=0;
            int prv=C;
            dfs1(i,0),
            dfsC(i),dfs2(i,0);
            for(int j=prv;j++<C;)
                if(cycles.par[j]==j)
                    adj2[par[j]].push_back(j);
            dfs3(i);
        }
    }
    cout<<res<<'\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