Submission #1143089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143089		Math4Life2020	Duathlon (APIO18_duathlon)	C++20	100 / 100	77 ms	32704 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
ll ans = 0;
ll N,M; const ll Nm = 1e5+5; const ll E = 20; const ll INF = 1e18;
vector<ll> adj[Nm];
vector<bool> found(Nm,0);
vector<ll> radj(Nm,-1);
vector<ll> fadj[Nm];
vector<ll> rmin(Nm,INF);
vector<ll> ht(Nm,0);
vector<bool> ijrev(Nm,0); //is a reverse jump?
vector<ll> gsz(Nm,0); //group size
vector<ll> gind(Nm,-1);
vector<ll> gelem[Nm]; //group elements

void dfs1(ll x) {
    found[x]=1;
    for (ll y: adj[x]) {
        if (!found[y]) {
            fadj[x].push_back(y);
            ht[y]=1+ht[x];
            radj[y]=x;
            dfs1(y);
            rmin[x]=min(rmin[x],rmin[y]);
        } else {
            if (y!=radj[x] && ht[y]<ht[x]) {
                rmin[x]=min(rmin[x],ht[y]);
            }
        }
    }
    if (rmin[x]>=(ht[x]-1)) {
        ijrev[x]=1;
        //cout << "ijrev=1 at x="<<x<<"\n";
    }
}

void dfs2(ll x) {
    gsz[gind[x]]++;
    gelem[gind[x]].push_back(x);
    for (ll y: fadj[x]) {
        if (ijrev[y]) {
            gind[y]=y;
            dfs2(y);
        } else {
            gind[y]=gind[x];
            dfs2(y);
        }
    }
}

vector<ll> p1(Nm,0); //sum of in1
vector<ll> p2(Nm,0); //sum of in2
vector<ll> p1q(Nm,0); //sum of (in1)^2
vector<ll> p12(Nm,0);

void dfs3(ll x) {
    for (ll y: fadj[x]) {
        dfs3(y);
    }
    if (!ijrev[x]) {
        return;
    }
    ll SZ = gsz[x];
   // cout << "x="<<x<<", SZ="<<SZ<<"\n";
    if (SZ==1) {
       // cout << "p1[x]="<<p1[x]<<",p2[x]="<<p2[x]<<",p12[x]="<<p12[x]<<",p1q[x]="<<p1q[x]<<"\n";
        ans += (p1[x]*p2[x]-p12[x])+(p1[x]*p1[x]-p1q[x])/2 + p2[x];
        ll n1 = 1+p1[x];
        ll n2 = p1[x]+p2[x];
        //cout << "n1,n2="<<n1<<","<<n2<<"\n";
        if (radj[x]!=-1) {
            ll y = radj[x];
            //cout << "y="<<y<<"\n";
            p1[y]+=n1;
            p1q[y]+=n1*n1;
            p2[y]+=n2;
            p12[y]+=n1*n2;
        }
        return;
    }
    //cout << "PROCESS BODY: x="<<x<<"\n";
    //cout << "ans0="<<ans<<"\n";
    if (SZ>=2) {
        SZ++;
    }
    ll sp1 = 0;
    ll sp2 = 0;
    ll sp12 = 0;
    ll sp11 = 0;
    for (ll y: gelem[x]) {
        //cout << "element: "<<y<<"\n";
        sp1 += p1[y];
        sp2 += p2[y];
        sp12 += p12[y];
        sp11 += p1[y]*p1[y];
        ans += (p1[y]*p1[y]-p1q[y])/2;
    }
    ll n1 = SZ-1+sp1;
    ll n2 = ((SZ-1)*(SZ-2)) + sp2 + (SZ-1)*sp1;
    ans += SZ*(sp1*sp1-sp11)/2;
    ans += (SZ-1)*(SZ-2)*(SZ-3)/2; //all internal
    ans += (SZ-1)*(SZ-2)/2; //middle at top point
    ans += (SZ-1)*(SZ-2)*sp1;
    ans += (sp1*sp2-sp12);
    ans += sp2*(SZ-1);
    //cout << "n1,n2="<<n1<<","<<n2<<"\n";
    if (radj[x]!=-1) {
        ll y = radj[x];
        p1[y]+=n1;
        p1q[y]+=n1*n1;
        p2[y]+=n2;
        p12[y]+=n1*n2;
    }
    //cout << "ansf="<<ans<<"\n";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M;
    for (ll i=0;i<M;i++) {
        ll u,v; cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (ll i=0;i<N;i++) {
        if (!found[i]) {
            ht[i]=0;
            dfs1(i);
            gind[i]=i;
            dfs2(i);
            dfs3(i);
        }
    }
    cout << (2*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