Submission #977870

#	Time	Username	Problem	Language	Result	Execution time	Memory
977870		huutuan	Duathlon (APIO18_duathlon)	C++14	0 / 100	103 ms	42536 KiB

count_triplets

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=2e5+10;
int n, m;
vector<int> g[N];
int num[N], low[N], tdfs;
stack<pair<int, int>> stk;
vector<pair<int, int>> bcc[N];
int cnt=0, cc[N], sz[N];
bool joint[N];
vector<int> gg[N];

void dfs_joint(int u, int p){
   num[u]=low[u]=++tdfs;
   int child=0;
   for (int v:g[u]){
      if (v==p) continue;
      if (!num[v]){
         ++child;
         stk.emplace(u, v);
         dfs_joint(v, u);
         low[u]=min(low[u], low[v]);
         if (low[v]>=num[u]){
            joint[u]=1;
            ++cnt;
            pair<int, int> edge={-1, -1};
            do{
               edge=stk.top(); stk.pop();
               bcc[cnt].emplace_back(edge);
            }while (edge!=make_pair(u, v));
         }
      }else low[u]=min(low[u], num[v]);
   }
   if (!p) joint[u]=child>=2;
}

int ans;

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   for (int i=1; i<=m; ++i){
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   dfs_joint(1, 0);
   set<pair<int, int>> edge;
   for (int i=1; i<=n; ++i) if (joint[i]) cc[i]=i;
   for (int i=1; i<=cnt; ++i){
      for (auto &j:bcc[i]){
         if (!joint[j.first]) cc[j.first]=n+i;
         else edge.emplace(n+i, j.first);
         if (!joint[j.second]) cc[j.second]=n+i;
         else edge.emplace(n+i, j.second);
      }
   }
   for (int i=1; i<=n; ++i) ++sz[cc[i]];
   for (auto &i:edge){
      gg[i.first].push_back(i.second);
      gg[i.second].push_back(i.first);
   }
   ans=n*(n-1)*(n-2);
   int ff=0;
   for (int i=1; i<=n; ++i) if (!joint[i] && g[i].size()==1){
      ans-=(n-1)*(n-2);
      ++ff;
   }
   for (int i=1; i<=n; ++i) if (!joint[i] && g[i].size()==1){
      ans-=(n-ff-1)*2;
   }
   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