Submission #1094595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094595		flying_saucer	Duathlon (APIO18_duathlon)	C++14	8 / 100	45 ms	43468 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

typedef pair<long long,long long> PLL;
typedef long long LL;

#define ln '\n'
#define faster {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}

#define all(v) v.begin(),v.end()

int mod = 998244353;
const int N = 4e5 + 10;
const int inf = 1e9;

bitset <N> art, good;
vector <int> g[N], tree[N], st, comp[N];
int n, m, ptr, cur, in[N], low[N], id[N];

void dfs (int u, int from, int &SZ) {
  in[u] = low[u] = ++ptr; SZ++;
  st.emplace_back(u);
  for (int v : g[u]) if (v ^ from) {
    if (!in[v]) {
      dfs(v, u, SZ);
      low[u] = min(low[u], low[v]);
      if (low[v] >= in[u]) {
        art[u] = in[u] > 1 or in[v] > 2;
        comp[++cur].emplace_back(u);
        while (comp[cur].back() ^ v) {
          comp[cur].emplace_back(st.back());
          st.pop_back();
        }
      } 
    } else {
      low[u] = min(low[u], in[v]);
    }
  }
}

void buildTree(int n) {
  ptr = 0;
  for (int i = 1; i <= n; ++i) {
    if (art[i]) id[i] = ++ptr;
  }
  for (int i = 1; i <= cur; ++i) {
    int x = ++ptr;
    for (int u : comp[i]) {
      if (art[u]) {
        tree[x].emplace_back(id[u]);
        tree[id[u]].emplace_back(x);
      } else {
        id[u] = x;
      }
    }
  }
}

void solve(int test){
    int n, m, q; cin>>n>>m;
    for(int i = 0, u, v; i < m; i++){
        cin>>u>>v;
        g[u].push_back(v); g[v].push_back(u);
    }

    auto nC2 = [&](LL n){
        return n * (n - 1) / 2;
    };
    auto nC3 = [&](LL n){
        return n * (n - 1) * (n - 2) / 6;
    };
    LL ans = 0;
    for(int i = 1; i <= n; i++){
        if(!in[i]){
            int SZ = 0, last = cur + 1;
            dfs(i, -1, SZ);
            ans += nC3(SZ);
            for(int j = last; j <= cur; j++){
                int sz = comp[j].size();
                int artP = 0;
                for(int k = 0; k < sz; k++)
                    artP += art[comp[j][k]];
                LL tmp = nC3(sz) * 2 + nC2(sz - 1) * (SZ - sz);
                ans += tmp;
            }
        }
    }
    
    cout<<ans * 2<<'\n';
}

signed main(){
    faster
    int t = 1; 
    // cin>>t;
    for(int i = 1; i <= t; i++){
        solve(i);
    }
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void solve(int)':
count_triplets.cpp:61:15: warning: unused variable 'q' [-Wunused-variable]
   61 |     int n, m, q; cin>>n>>m;
      |               ^

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