Submission #97141

#	Time	Username	Problem	Language	Result	Execution time	Memory
97141		fefe	Duathlon (APIO18_duathlon)	C++17	100 / 100	275 ms	29388 KiB

count_triplets

#include<bits/stdc++.h>
#define MAX_N 100005
#define MAX_M 200005
#define pb push_back
#define mp make_pair
#define all(V) (V).begin(),(V).end()
#define reset(V) (V).clear();(V).resize(0);
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))
#define fi first
#define se second
#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
#define inf 0x3fffffff
#define MOD 1000000007LL
#define cpx_mod(x) (((LD)(((LL)x.real())%MOD)),((LD)(((LL)x.imag())%MOD)))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef pair<LL,string> pls;
typedef complex<LD> Complex;
typedef long double LD;
int n,m,ln,dep[MAX_N],loc[MAX_N],val[MAX_N];
LL ans;
bool vis[MAX_N];
vector<int> E[MAX_N],L,lst[MAX_N];
vector<pii> bcc[MAX_N];
void merge(int x,int y){
	int p,q;
	p=loc[x];
	q=loc[y];
	if(bcc[p].size()<bcc[q].size())	swap(p,q);
	loc[x]=p;
	while(bcc[q].size()){
		bcc[p].pb(bcc[q].back());		
		bcc[q].pop_back();
	}
}
int make_bcc(int x){
	int z=dep[x]-1,k;
	m++;
	loc[x]=ln++;
	bcc[loc[x]].pb({x,0});
	for(int y:E[x]){
		if(dep[y]){
			z=min(z,dep[y]);
			continue;
		}
		dep[y]=dep[x]+1;
		k=make_bcc(y);
		z=min(z,k);
		if(k==dep[x]){
			bcc[loc[y]].pb({x,0});
			L.pb(loc[y]);
			continue;
		}
		merge(x,y);
	}
	return z;
}
int dfs(int x,int y){
	int sum=0;
	vis[x]=true;
	for(pii &p:bcc[x]){
		p.se++;
		if(p.fi==y)	continue;
		for(int q:lst[p.fi]){
			if(vis[q])	continue;
			p.se+=dfs(q,p.fi)-1;
		}
	}
	for(pii p:bcc[x])	sum+=p.se;
	for(pii &p:bcc[x]){
		if(p.fi==y)	p.se=m-sum+1;
		ans+=((LL)(bcc[x].size()-2))*(LL)p.se*((LL)(m-p.se));
		ans+=2*((LL)val[p.fi])*((LL)(m-p.se));
		val[p.fi]+=(m-p.se);
	}
	return sum;
}
int main(){
	int i,x,y;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d %d",&x,&y);
		E[x].pb(y);
		E[y].pb(x);
	}
	for(i=1;i<=n;i++){
		if(dep[i])	continue;
		L.clear();
		L.resize(0);
		dep[i]=1;
		m=0;
		make_bcc(i);
		if(m<2)	continue;
		for(int p:L){
			for(pii z:bcc[p]){
				lst[z.fi].pb(p);
			}
		}
		x=bcc[L[0]][0].fi;
		for(int q:lst[x]){
			dfs(q,x);
		}
	}	
	for(i=1;i<=n;i++)	dep[i]=0;	//dep --> count node under me
	
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:86: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:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

• 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