Submission #906691

#	Time	Username	Problem	Language	Result	Execution time	Memory
906691		andrei_boaca	Duathlon (APIO18_duathlon)	C++17	31 / 100	246 ms	37344 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
ll n,m,par[100005],use[100005],niv[100005],nivmin[100005];
map<pii,int> f;
vector<int> muchii[100005];
vector<int> edges[100005];
ll nrcomp;
ll comp[100005],sz[100005],nr[100005],ans;
ll total;
void dfs(int nod)
{
    use[nod]=1;
    nivmin[nod]=niv[nod];
    for(int i:muchii[nod])
    {
        if(i==par[nod])
            continue;
        if(!use[i])
        {
            par[i]=nod;
            niv[i]=niv[nod]+1;
            dfs(i);
            nivmin[nod]=min(nivmin[nod],nivmin[i]);
            if(niv[nod]<nivmin[i])
                f[{nod,i}]=f[{i,nod}]=1;
        }
        else
            nivmin[nod]=min(nivmin[nod],niv[i]);
    }
}
void build(ll nod)
{
    sz[nrcomp]++;
    comp[nod]=nrcomp;
    for(int i:muchii[nod])
        if(comp[i]==0&&f.count({nod,i})==0)
            build(i);
}
void initgo(ll nod)
{
    use[nod]=1;
    total+=sz[nod];
    for(int i:edges[nod])
        if(!use[i])
            initgo(i);
}
void go(ll nod)
{
    nr[nod]=sz[nod];
    vector<ll> vals;
    for(ll i:edges[nod])
        if(i!=par[nod])
        {
            par[i]=nod;
            go(i);
            vals.push_back(nr[i]);
            nr[nod]+=nr[i];
        }
    vals.push_back(total-nr[nod]);
    ll val=sz[nod]*(sz[nod]-1)*(sz[nod]-2);
    ans+=val;
    ll suma=0;
    for(ll i:vals)
    {
        ll a=2LL*sz[nod]*i*suma;
        suma+=i;
        ans+=a;
        a=((sz[nod]-1)*(sz[nod]-2)*i+(sz[nod]-1)*i)*2LL;
        ans+=a;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        if(!use[i])
        {
            niv[i]=1;
            dfs(i);
        }
    for(int i=1;i<=n;i++)
        if(!comp[i])
        {
            nrcomp++;
            build(i);
        }
    for(auto i:f)
    {
        ll a=i.first.first;
        ll b=i.first.second;
        a=comp[a];
        b=comp[b];
        edges[a].push_back(b);
    }
    for(int i=1;i<=n;i++)
    {
        use[i]=0;
        par[i]=0;
    }
    for(int i=1;i<=nrcomp;i++)
        if(!use[i])
        {
            total=0;
            initgo(i);
            go(i);
        }
    cout<<ans;
    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