Submission #1141025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141025		Math4Life2020	Duathlon (APIO18_duathlon)	C++20	0 / 100	124 ms	27920 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
ll N,M;
const ll Nm = 1e5+5;
ll ans = 0;
vector<ll> adj[Nm];
vector<bool> found(Nm,0);
vector<bool> brd(Nm,0); //is x->radj[x] a bridge?
ll radj[Nm]; //reverse adjacency (tree)
vector<ll> fadj[Nm]; //forward adjacency (tree)
ll ht[Nm]; //height in tree
vector<ll> nbwd(Nm,0); //number of backward edges (total)

vector<ll> pind(Nm,-1); //point index
vector<ll> pcnt(Nm,0); //point index: how many points at this index
vector<ll> pradj(Nm,-1); //point radj
vector<ll> pfadj[Nm]; //point fadj

void dfs(ll x) {
   // cout << "process x="<<x<<"\n";
    found[x]=1;
    for (ll y: adj[x]) {
        if (y==radj[x]) {
            continue;
        }
        if (!found[y]) {
            fadj[x].push_back(y);
            ht[y]=1+ht[x];
            radj[y]=x;
            dfs(y);
        } else {
            if (ht[y]>ht[x]) {
                continue;
            }
            //y must be an ancestor of x
            nbwd[y]--;
            nbwd[x]++;
           // cout << "incr x="<<x<<", decr y="<<y<<"\n";
        }
    }
    for (ll y: fadj[x]) {
        nbwd[x] += nbwd[y];
    }
    // if (x==0) {
    //     assert(nbwd[x]==0);
    // }
    //cout << "nbwd[x]="<<nbwd[x]<<"\n";
    if (nbwd[x]==0) {
        brd[x]=1;
    } else {
        brd[x]=0;
    }
}

void dfs2(ll x) {
    if (brd[x]) {
        pind[x]=x;
        if (x==0) {
            pradj[x]=-1;
        } else {
            assert(radj[x]!=-1);
            pradj[x]=pind[radj[x]];
            pfadj[pind[radj[x]]].push_back(x);
        }
    } else {
        assert(radj[x]!=-1);
        pind[x]=pind[radj[x]];
    }
    pcnt[pind[x]]++;
    for (ll y: fadj[x]) {
        dfs2(y);
    }
}

pii dfs3(ll x) {
    ll k = pcnt[x];
    //cout << "dfs3: x="<<x<<", k="<<k<<"\n";
    ll s1=0;
    ll s2=0;
    ll s11=0;
    ll s12=0;
    for (ll y: pfadj[x]) {
        pii pt = dfs3(y);
        s1 += pt.first;
        s2 += pt.second;
        s11 += pt.first*pt.first;
        s12 += pt.first*pt.second;
    }
    ans += k*s2;
    //cout << (k*s2) << "\n";
    ans += k*(s1*s1-s11)/2;
    ans += ((k-1)*(k-1))*s1;
    ans += (s1*s2-s12);
    ans += (k*(k-1)*(k-2))/2;
    //cout << (k*(k-1)*(k-2))/2 << "\n";
    ll t1 = 0; ll t2 = 0;
    t2 += (k-1)*(k-1);
    t2 += s2;
    t2 += k*s1;
    t1 += k;
    t1 += s1;
    return {t1,t2};
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M;
    for (ll m=0;m<M;m++) {
        ll a,b; cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    radj[0]=-1;
    ht[0]=0;
    dfs(0);
    dfs2(0);
    dfs3(0);
    ans = ans*2;
    cout << ans <<"\n";
}

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