Submission #1172884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172884		escobrand	Duathlon (APIO18_duathlon)	C++20	0 / 100	33 ms	20292 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define eb push_back
#define ll long long 
#define fi first
#define se second
int t,n,i,m,u,v;
const int maxn = 2e5 + 10;
bool c[maxn],e[maxn];
vector<pair<int,int>> a[maxn];
ll sum[maxn],s[maxn],tim[maxn],ans,bo[maxn],tim_bo[maxn],tmp;
int de[maxn];
void pre(int i,int p)
{
  c[i] = 1;
  s[i] = 1;
  de[i] = de[p]+1;
  for(auto [k,id] : a[i])
  {
    if(k == p)continue;
    if(c[k])
    {
      if(de[k] < de[i])
      {
        e[id] = 1;
        // cout<<i<<' '<<k<<'\n';
      }
    }
    else
    {
      pre(k,i);
      s[i] += s[k];
      sum[i] += sum[k];
      tim[i] += tim[k];
    }
  }
  sum[i] -= tim[i];
  tim[i] -= tim_bo[i];
  sum[i] -= n * tim_bo[i] - bo[i];
  
  ans += sum[i];
  // cout<<i<<' '<<sum[i]<<'\n';
  sum[i] += s[i]-1;
  for(auto [k,id] : a[i])
  {
    if(k == p)continue;
    if(e[id] && de[k] < de[i])
    {
      tim[i]++;
      sum[i]+= n - s[i];
      tim_bo[k]++;
      bo[k] += s[i] + de[i] - de[k];
      tmp = de[i] - de[k];
      ans += (tmp-1)*tmp / 2;
    }
  }
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>m;
    
    for(i = 1;i<=m;i++)
    {
      cin>>u>>v;
      a[u].eb({v,i});
      a[v].eb({u,i});
    }
    
    pre(1,0);
    // for(i = 1;i<=n;i++)cout<<tim[i]<<' ';
    cout<<ans * 2;
    
    return 0;
}

• 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