Submission #1173560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173560		escobrand	Duathlon (APIO18_duathlon)	C++20	100 / 100	86 ms	35724 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define eb emplace_back
#define ll long long 
#define fi first
#define se second
int t,n,i,m,j,u,v,co;
const int maxn = 3e5 + 10;
vector<int> a[maxn],tree[maxn];
int tim[maxn],low[maxn],s[maxn];
stack<int> st;
ll ans,N;

void dfs(int i,int p)
{
  // cout<<i<<'\n';
  N++;
  tim[i] = low[i] = ++t;
  st.push(i);
  for(int k : a[i])
  {
    if(k == p)continue;
    if(tim[k])low[i] = min(low[i],tim[k]);
    else
    {
      dfs(k,i);
      low[i] = min(low[i],low[k]);
      if(low[k] >= tim[i])
      {
        co++;
        tree[i].eb(n+co);
        while(st.top() != k)
        {
          tree[n+co].eb(st.top());
          st.pop();
        }
        tree[n+co].eb(st.top());
        st.pop();
      }
    }
  }
}

void cal(int i,int p)
{
  s[i] = (i <= n);
  for(int k : tree[i])
  {
    if(k == p)continue;
    cal(k,i);
    s[i] += s[k];
    if(i > n)ans -= tree[i].size() * s[k] * (s[k]-1);
  }
  if(i > n)ans -= tree[i].size() * (N - s[i]) * (N - s[i] - 1);
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m;
    while(m--)
    {
      cin>>u>>v;
      a[u].eb(v);
      a[v].eb(u);
    }
    
    for(i = 1;i<=n;i++)
    {
      if(!tim[i])
      {
        N = 0;
        dfs(i,0);
        ans += N * (N - 1) * (N - 2);
        // cout<<i<<' '<<ans<<'\n';
        cal(i,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