Submission #1118731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118731		boclobanchat	Duathlon (APIO18_duathlon)	C++14	31 / 100	130 ms	31868 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=1e5+5;
vector<int> ds[MAXN],sd[MAXN],vi[MAXN],ve[MAXN];
vector<ii> edge;
stack<int> st;
int low[MAXN],num[MAXN],col[MAXN],sub[MAXN],root[MAXN],tdfs=0,cnt=0;
long long ans=0,c=0,tp[MAXN],T[MAXN],tt[MAXN];
void dfs(int i,int pre)
{
	low[i]=num[i]=++tdfs;
	for(auto v:ds[i])
	{
		if(v==pre) continue;
		if(!num[v])
		{
			dfs(v,i);
			low[i]=min(low[i],low[v]);
			if(low[v]==num[v]) edge.push_back({i,v});
			else sd[i].push_back(v),sd[v].push_back(i);
		}
		else low[i]=min(low[i],num[v]),sd[i].push_back(v),sd[v].push_back(i);
	}
}
void dfsus(int i)
{
	c++,col[i]=cnt;
	for(auto v:sd[i]) if(!col[v]) dfsus(v);
}
void dftree(int i,int pre)
{
	st.push(i),sub[i]=1,root[i]=pre;
	for(auto v:vi[i]) if(v!=pre)
	{
		dftree(v,i);
		sub[i]+=sub[v],tp[i]+=tp[v];
	}
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	int l,r;
    	cin>>l>>r;
    	ds[l].push_back(r),ds[r].push_back(l);
	}
	for(int i=1;i<=n;i++) if(!num[i]) dfs(i,i);
	for(int i=1;i<=n;i++) if(!col[i])
	{
		cnt++,c=0;
		dfsus(i);
		ans+=c*(c-1)*(c-2),tp[cnt]=T[cnt]=c;
	}
	for(auto v:edge)
	{
		vi[col[v.fi]].push_back(col[v.se]),vi[col[v.se]].push_back(col[v.fi]);
		ve[v.fi].push_back(v.se),ve[v.se].push_back(v.fi);
	}
	for(int i=1;i<=cnt;i++) if(!sub[i])
	{
		dftree(i,i);
		while(!st.empty()) tt[st.top()]=tp[i],st.pop();
	}
	for(int i=1;i<=cnt;i++)
	{
		ans+=T[i]*(tt[i]-T[i])*(tt[i]-T[i]);
		for(auto v:vi[i]) if(v==root[i]) ans-=T[i]*(tt[i]-tp[i])*(tt[i]-tp[i]);
		else ans-=T[i]*tp[v]*tp[v];
	}
	for(int i=1;i<=n;i++)
	{
		int cc=col[i];
		ans+=(T[cc]-1)*(tt[cc]-T[cc])*2;
		for(auto v:ve[i]) if(root[cc]==col[v]) ans-=(T[cc]-1)*(tt[cc]-tp[cc])*2;
		else ans-=(T[cc]-1)*tp[col[v]]*2;
	}
	cout<<ans;
}

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