Submission #1265259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265259		escobrand	Duathlon (APIO18_duathlon)	C++20	23 / 100	80 ms	36168 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define mk make_pair
typedef pair<int,int> pii;

const int maxn  = 1e5 + 10;
int i,n,t,u,v,m;
vector<int> adj[maxn],bcc[maxn],com_adj[maxn *2];
int low[maxn],tim[maxn],com_cnt,com[maxn];
stack<int> st;
bool crit[maxn];

void dfs(int i,int pa)
{
  int child = 0;
  low[i] = tim[i] = ++t;
  st.push(i);
  for(int k : adj[i])
  {
    if(k == pa)continue;
    if(tim[k])low[i]= min(low[i],tim[k]);
    else 
    {
      child++;
      dfs(k,i);
      low[i] = min(low[i],low[k]);
      
      if(pa == 0 && child >= 2)crit[i] = 1;
      if(pa && low[k] >= tim[i])crit[i] = 1;
      
      if(low[k] >= tim[i])
      {
        com_cnt++;
        while(st.top() != k)
        {
          bcc[com_cnt].pb(st.top());
          st.pop();
        }
        bcc[com_cnt].pb(st.top());
        st.pop();
        bcc[com_cnt].pb(i);
      }
    }
  }
}

ll dp[maxn*2][2];
ll s[maxn * 2],ans;
bool c[maxn*2];

void cal(int i,int pa)
{
  c[i] = 1;
  dp[i][0] = s[i];
  dp[i][1] = s[i] * (s[i]-1);
  ll tmp = 0;
  for(int k : com_adj[i])
  {
    if(k == pa)continue;
    cal(k,i);
    if(i <= n)tmp += s[k] * (s[k]-1)/2;
    tmp += dp[i][0] * dp[k][1];
    tmp += dp[i][1] * dp[k][0];
    dp[i][0] += dp[k][0];
    dp[i][1] += dp[k][1];
    dp[i][1] += s[i] * dp[k][0];
  }
  ans += tmp;
  // cout<<i<<' '<<dp[i][0]<<' '<<dp[i][1]<<' '<<tmp<<'\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>m;
    while(m--)
    {
      cin>>u>>v;
      adj[u].pb(v);
      adj[v].pb(u);
    }
    
    for(i = 1;i<=n;i++)
    {
      if(!tim[i])
      {
        dfs(i,0);
        if(st.size())
        {
          if(st.size() > 1)
          {
            com_cnt++;
            for(;st.size();st.pop())bcc[com_cnt].pb(st.top());
          }
          else st.pop();
        }
      }
    }
    
    for(i = 1;i<=com_cnt;i++)
    {
      for(int k : bcc[i])
      {
        if(crit[k])
        {
          com[k] = k;
          com_adj[k].pb(n+i);
          com_adj[n+i].pb(k);
          s[k] = 1;
        }
        else 
        {
          com[k] = n + i;
          s[com[k]]++;
        }
      }
    }
    
    for(i = 1;i<=n;i++)
    {
      int tmp = com[i];
      // cout<<i<<' '<<tmp<<' '<<s[tmp]<<'\n';
      if(!c[tmp])
      {
        cal(tmp,0);
      }
    }
    
    cout<<ans * 2;
    
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 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