Submission #1166983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166983		Zero_OP	Duathlon (APIO18_duathlon)	C++20	0 / 100	107 ms	36936 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pb push_back
#define eb emplace_back

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vd = vector<db>;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

const int MAX = 3e5 + 5;

int N, M, low[MAX], num[MAX], sub[MAX], timer_dfs, used;
vi adj[MAX], adj_bcc[MAX];
stack<int> st;
ll ans;

struct DSU{
      vi lab;
      DSU(int n) : lab(n, -1) {}

      int root(int u){ return lab[u] < 0 ? u : (lab[u] = root(lab[u])); }
      bool join(int u, int v){
            u = root(u);
            v = root(v);
            if(u == v) return false;
            if(lab[u] > lab[v]) swap(u, v);
            lab[u] += lab[v];
            lab[v] = u;
            return true;
      }
};

void tarjan(int u, int p){
      low[u] = num[u] = ++timer_dfs;
      st.push(u);

      for(auto v : adj[u]) if(v != p){
            if(num[v]) minimize(low[u], num[v]);
            else{
                  tarjan(v, u);
                  minimize(low[u], low[v]);
                  if(low[v] >= num[u]){
                        adj_bcc[used].pb(u);
                        adj_bcc[u].pb(used);

                        while(adj_bcc[used].back() != v){
                              adj_bcc[used].pb(st.top());
                              adj_bcc[st.top()].pb(used);
                              st.pop();
                        }

                        ++used;
                  }
            }
      }
}

void dfs_tree(int u, int p){
      sub[u] = (u < N);
      for(auto v : adj_bcc[u]) if(v != p){
            dfs_tree(v, u);
            sub[u] += sub[v];
            if(u >= N){
                  ans -= 1LL * (sz(adj_bcc[u]) - 1) * sub[v] * (sub[v] - 1);
            }
      }

      if(u >= N){
            ans -= 1LL * (sz(adj_bcc[u]) - 1) * (N - sub[u]) * (N - sub[u] - 1);
      }
}

int main(){
      setIO();

      cin >> N >> M;

      DSU dsu(N);
      while(M--){
            int u, v;
            cin >> u >> v;
            --u, --v;
            adj[u].pb(v);
            adj[v].pb(u);
            dsu.join(u, v);
      }

      ans = 0;
      used = N;
      FOR(i, 0, N) if(dsu.root(i) == i){
            timer_dfs = 0;
            tarjan(i, -1);
            ans += 1LL * timer_dfs * (timer_dfs - 1) * (timer_dfs - 2);
            dfs_tree(i, -1);
      }

      cout << ans << '\n';

      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