Submission #103723

#	Time	Username	Problem	Language	Result	Execution time	Memory
103723		autumn_eel	Duathlon (APIO18_duathlon)	C++14	0 / 100	212 ms	48272 KiB

count_triplets

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

struct BCC{
	int n;
	vector<vector<P>>E;
	vector<bool>used;
	vector<int>dep,low,cmp,cnt;
	vector<P>bridge;
	vector<P>es;
	
	void dfs(int v,int p,int d){
		used[v]=true;
		low[v]=dep[v]=d;
		for(auto&u:E[v]){
			if(u.second==p)continue;
			if(used[u.second]){
				low[v]=min(low[v],dep[u.second]);
				continue;
			}
			dfs(u.second,v,d+1);
			if(dep[v]<low[u.second]){
				bridge.push_back(P(u.second,v));
				u.first=true;
			}
			low[v]=min(low[v],low[u.second]);
		}
	}
	void dfs2(int v,int k){
		cmp[v]=k;
		cnt[k]++;
		for(auto&u:E[v]){
			if(u.first||cmp[u.second]!=-1)continue;
			dfs2(u.second,k);
		}
	}
	BCC(vector<vector<P>>E):E(E){
		n=E.size();
		used=vector<bool>(n);
		dep=low=vector<int>(n);
		cmp=vector<int>(n,-1);
		rep(i,n){
			if(!used[i])dfs(i,-1,0);
		}
		int c=0;
		rep(i,n){
			if(cmp[i]==-1){
				cnt.push_back(0);
				dfs2(i,c++);
			}
		}
		for(auto p:bridge){
			es.push_back(P(cmp[p.first],cmp[p.second]));
		}
	}
	vector<int>getvs(){
		return cnt;
	}
	vector<P>getes(){
		return es;
	}
};

int n,m;
vector<int>E[200000];
int sz[200000];
bool used1[200000],used2[200000];
vector<int>vs;

ll ans=0;
int cnt=0;
 
void dfs1(int v){
	cnt+=vs[v];
	used1[v]=true;
	for(int u:E[v]){
		if(used1[u])continue;
		dfs1(u);
	}
}
void dfs2(int v,int p){
	used2[v]=true;
	int s=cnt-vs[v];
	sz[v]=vs[v];
	for(int u:E[v]){
		if(used2[u])continue;
		dfs2(u,v);
		sz[v]+=sz[u];
		s-=sz[u];
		ans+=sz[u]*(ll)(cnt-sz[u]-vs[v]);
	}
	ans+=s*(ll)(cnt-s-vs[v]);
	if(vs[v]>1){
		ans+=(ll)(cnt-vs[v])*(vs[v]-1)*(vs[v]-1)*2;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	vector<vector<P>>G(n);
	rep(i,m){
		int a,b;scanf("%d%d",&a,&b);a--;b--;
		G[a].push_back(P(0,b));
		G[b].push_back(P(0,a));
	}
	BCC bcc(G);
	vs=bcc.getvs();
	auto res=bcc.getes();
	for(auto p:res){
		E[p.first].push_back(p.second);
		E[p.second].push_back(p.first);
	}
	for(int i:vs){
		if(i>=3){
			ans+=i*(ll)(i-1)*(ll)(i-2);
		}
	}
	rep(i,n){
		if(!used1[i]){
			cnt=0;
			dfs1(i);
			dfs2(i,-1);
		}
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:104:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a,b;scanf("%d%d",&a,&b);a--;b--;
           ~~~~~^~~~~~~~~~~~~~

• 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