Submission #1172459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172459		escobrand	Duathlon (APIO18_duathlon)	C++20	0 / 100	31 ms	16520 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 = 1e5 + 10;
bool c[maxn],e[maxn*2];
vector<pair<int,int>> a[maxn];
ll sum[maxn],s[maxn],tim[maxn],ans;
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] + s[k]-1;
      tim[i] += tim[k];
    }
  }
  sum[i] -= tim[i];
  ans+=sum[i];
  // cout<<i<<' '<<sum[i]<<'\n';
  for(auto [k,id] : a[i])
  {
    if(k == p)continue;
    if(e[id] && de[k] < de[i])
    {
      tim[i]++;
      sum[i]+= n - s[i];
    }
  }
  
  
}



int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    
    cin>>n>>m;
    
    for(i = 0;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