Submission #1265267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265267		escobrand	Duathlon (APIO18_duathlon)	C++20	100 / 100	74 ms	35396 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];
ll s[maxn * 2],ans,ex[maxn * 2],N;
bool c[maxn*2];

void prep(int i,int pa)
{
  c[i] = 1;
  dp[i] = s[i];
  for(int k : com_adj[i])
  {
    if(k == pa)continue;
    prep(k,i);
    dp[i] += dp[k];
  }
}

void cal(int i,int pa)
{ 
  for(int k : com_adj[i])
  {
    if(k == pa)continue;
    cal(k,i);
    if(i > n)ans -= (s[i] + ex[i]-1) * dp[k] * (dp[k]-1);
  }
  if(i > n)ans -= (s[i] + ex[i]-1) * (N-dp[i]) * (N-dp[i]-1);
}

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;
          ex[n+i]++;
        }
        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])
      {
        prep(tmp,0);
        N = dp[tmp];
        ans += N * (N-1) * (N-2);
        cal(tmp,0);
      }
    }
    
    cout<<ans;
    
    return 0;
}

• 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