Submission #408999

#	Time	Username	Problem	Language	Result	Execution time	Memory
408999		juggernaut	Duathlon (APIO18_duathlon)	C++17	0 / 100	860 ms	1048580 KiB

count_triplets

//Subtask 1
//Subtask 2
//*Subtask 3
//*Subtask 4
//*Subtask 5
//Subtask 6
//Subtask 7
//Subtask 8
//Subtask 9
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
int n,m,timer,tin[100005],fup[100005];
vector<pair<int,bool>>g[100005];
vector<int>gr[100005];
bool vis[100005];
int new_id[100005];
int ver_sz[100005];
int sz[100005];
vector<pair<int,int>>bridges;
template<class T>void umin(T &a,T b){if(b<a)a=b;}
template<class T>void umax(T &a,T b){if(a<b)a=b;}
void dfs(int v,int p){
	tin[v]=fup[v]=++timer;
	vis[v]=true;
	for(auto &[to,is_bridge]:g[v])if(to!=p){
		if(vis[to])umin(fup[v],tin[to]);
		else{
			dfs(to,v);
			umin(fup[v],fup[to]);
			if(fup[to]>tin[v]){
				is_bridge=true;
				bridges.emplace_back(v,to);
			}
		}
	}
}
void enumerate(int v){
	vis[v]=true;
	new_id[v]=timer;
	ver_sz[timer]++;
	for(auto [to,is_bridge]:g[v])if(!is_bridge&&!vis[to])enumerate(to);
}
ll ans=0;
void go(int v,int p){
	sz[v]=ver_sz[v];
	vis[v]=true;
	for(int to:gr[v])if(to!=p){
		go(to,v);
		sz[v]+=sz[to];
	}
}
void calc(int v,int p,int root){
	ll tmp=ver_sz[v];
	//All inside circle
	ans+=tmp*(tmp-1)*(tmp-2);
	vector<ll>vec;
	ll sum=0;
	for(int to:gr[v])if(to!=p){
		vec.push_back(sz[to]);
		sum+=sz[to];
	}
	if(root^v){
		sum+=sz[root]-sz[v];
		vec.push_back(sz[root]-sz[v]);
	}
	//In cirle only center
	for(ll x:vec){
		sum-=x;
		ans+=tmp*x*sum;
		sum+=x;
	}
	//Start or Finish in circle
	ans+=2ll*sum*(tmp-1)*(tmp-1);
	for(int to:gr[v])if(to!=p)calc(to,v,root);
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].emplace_back(y,0);
		g[y].emplace_back(x,0);
	}
	for(int i=1;i<=n;i++)if(!vis[i])dfs(i,i);
	memset(vis,0,sizeof vis);
	timer=0;
	for(int i=1;i<=n;i++)if(!vis[i]){
		timer++;
		enumerate(i);
	}
	for(int i=1;i<=n;i++)g[i].clear();
	memset(vis,0,sizeof vis);
	for(auto [x,y]:bridges){
		x=new_id[x];
		y=new_id[y];
		gr[x].push_back(y);
		gr[y].push_back(x);
	}
	for(int i=1;i<=timer;i++)if(!vis[i])go(i,i),calc(i,i,i);
	printf("%lld",ans);
}

Compilation message (stderr)

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

• 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