제출 #754225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
754225		bgnbvnbv	철인 이종 경기 (APIO18_duathlon)	C++14	0 / 100	129 ms	44216 KiB

count_triplets

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
stack< int > stt;
bool minimize(int &a, int b){ if (a>b) a=b; else return false; return true; }
bool maximize(int &a, int b){ if (a<b) a=b; else return false; return true; }
ll low[maxN],num[maxN],Time=0;
vector<ll>g[maxN];
ll cnt=0;
int lc[maxN];
vector<ll> ver;
vector<ll>bcc[maxN];
bool vis[maxN];
void DFS(int u){
   ver.pb(u);
   low[u]=num[u]=++Time;
   for (auto v:g[u]){
      if (num[v]) low[u]=min(low[u], num[v]);
      else {
         stt.push(u);
         DFS(v);
        low[u]=min(low[u], low[v]);
         if (low[v]>=num[u]) {
            cnt++;
            do {
               v=stt.top(); stt.pop();
               if (maximize(lc[v], cnt)==true) bcc[cnt].pb(v);
            } while (u!=v);
         }
      }
   }
   stt.push(u);
}
ll n,m,u,v;
ll ct[maxN],val[maxN],ans=0,vc=0;
vector<ll>adj[maxN];

void dfs(ll u,ll p)
{
    ct[u]=val[u];
    for(auto v:adj[u])
    {
        if(v!=p)
        {
            dfs(v,u);
            ct[u]+=ct[v];
        }
    }
    for(auto v:adj[u])
    {
        if(v!=p)
        {
            vc+=ct[v]*val[u]*(ct[u]-ct[v]-val[u]);
        }
    }
    vc+=(ct[u]-val[u])*val[u]*(ver.size()-ct[u]);
}
ll val2[maxN];
vector<ll>vec[maxN];
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int dm=1;dm<=n;dm++)
    {
        if(num[dm]>0) continue;
        ver.clear();
        for(int i=1;i<=cnt;i++) adj[i].clear(),bcc[i].clear();
        cnt=0;
        DFS(dm);
        for(int i=1;i<=cnt;i++)
        {
            for(auto zz:bcc[i])
            {
                vec[zz].pb(i);
            }
            if(bcc[i].size()>=3)
            {
                ll x=bcc[i].size();
                ans+=x*(x-1)*(x-2);
            }
            val[i]=bcc[i].size();
        }
        for(auto i:ver)
        {
            if(vec[i].size()==1) continue;
            cnt++;
            for(auto zz:vec[i])
            {
                adj[cnt].pb(zz);
                adj[zz].pb(cnt);
                val[zz]--;
            }
            val[cnt]++;
        }
        ll sum=0;
        for(int i=1;i<=cnt;i++)
        {
            val2[i]=val[i]*(val[i]-1);
            sum+=val2[i];
        }
        dfs(1,1);
        vc*=2;
        ans+=vc;
        //cout << ans << '\n';
        for(int i=1;i<=cnt;i++)
        {
            vc=sum-val2[i];
            for(auto j:adj[i])
            {
                vc-=val2[j];
            }
            ans+=vc*val[i];
            vc=ver.size()-val[i];
            for(auto j:adj[i])
            {
                vc-=val[j];
            }
            ans+=vc*val2[i];
        }
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

• 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