Submission #409048

#	Time	Username	Problem	Language	Result	Execution time	Memory
409048		Kerim	Duathlon (APIO18_duathlon)	C++17	100 / 100	232 ms	60600 KiB

count_triplets

#include "bits/stdc++.h"
#define MAXN 400009
#define ll long long
#define pb(x) push_back(x)
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
class Articulation {
  public:
    std::vector<int> keyV, bcc[MAXN];
    int cnt;
    int gao(int n, const std::vector<int> e[]) {
      memset(tag, use = 0, sizeof(tag[0]) * n);
      memset(low, cnt = 0, sizeof(low[0]) * n);
      std::fill_n(bcc, n, keyV = std::vector<int>());
      for (int i = 0; i < n; ++i) if (!tag[i]) dfs(i, 1, e);
      return cnt;
    }
  private:
    int tag[MAXN], low[MAXN], dot[MAXN], use;
    void dfs(int x, int dep, const std::vector<int> e[]) {
      int src = 0, out = 1 < dep; dot[use++] = x;
      tag[x] = low[x] = dep;
      for (auto &y: e[x]) {
        if (!tag[y]) {
          dfs(y, dep + 1, e);
          low[x] = std::min(low[x], low[y]);
          if (low[y] >= tag[x]) {
            if (++out == 2) keyV.push_back(x);
            while (dot[--use] != y) bcc[dot[use]].push_back(cnt);
            bcc[x].push_back(cnt); bcc[y].push_back(cnt++);
          }
        } else if (tag[y] != tag[x] - 1 || src++) {
          low[x] = std::min(low[x], tag[y]);
        }
      }
    }
} bcc;
vector<int> G[MAXN];
//APIO 2018 Duathlon
/*
	Articulation based BCC(Biconnected Component)
*/
vector<int>adj[MAXN];
void add(int u,int v){
	adj[u].pb(v);
	adj[v].pb(u);	
}
int vis[MAXN],sub[MAXN],n,m;
int comp_sz[MAXN];
void dfs(int nd,int pr){
	sub[nd]=(nd<n);
	vis[nd]=1;
	for(auto to:adj[nd])
		if(to!=pr)
			dfs(to,nd),sub[nd]+=sub[to];
}
ll C2(int x){
	return (x*1LL*(x-1));
}	
ll C3(int x){
	return (C2(x)*1LL*(x-2));	
}
ll ans=0;
void dfs1(int nd,int pr,int root){
	if(nd<n){
		for(auto to:adj[nd]){
			if(to!=pr){
				ans-=(comp_sz[to]-1)*1LL*C2(sub[root]-sub[to]);
				dfs1(to,nd,root);
			}
			else{
				ans-=(comp_sz[to]-1)*1LL*C2(sub[nd]);
			}
		}
	}
	else{
		for(auto to:adj[nd])
			if(to!=pr)
				dfs1(to,nd,root);	
	}
}
int main(){
	//freopen("file.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
    	int u,v;
		scanf("%d%d",&u,&v);
		u--;v--;
		G[u].pb(v);G[v].pb(u);
    }
    int C = bcc.gao(n,G);
    for(int i=0;i<n;i++)
    	for(auto to:bcc.bcc[i]){
    		add(i, to+n);
    		comp_sz[to+n]++;
    	}
    vector<int>roots;
    for(int i=n;i<n+C;i++)
    	if(!vis[i]){
    		roots.pb(i);
    		dfs(i,-1);
    	}
    for(auto root:roots){
    	ans+=C3(sub[root]);
    	dfs1(root,-1,root);
    }
    printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10