Submission #50346

#	Time	Username	Problem	Language	Result	Execution time	Memory
50346		zscoder	Duathlon (APIO18_duathlon)	C++17	100 / 100	359 ms	60096 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

vi adj[533113];
ll disc[533113];
ll low[533113];
vector<vector<ii> > bicon;
ll timer;
stack<ii> st;
bool isconn[533113];
bool isart[533113];
ll siz[510511];
vi tree[510511];
ll n,m; 

void dfs(ll u, ll p)
{
	disc[u]=++timer; ll child=0; low[u]=disc[u];
	for(ll v:adj[u])
	{
		if(v==p) continue;
		if(!disc[v])
		{
			child++;
			st.push(mp(u,v));
			dfs(v,u);
			low[u] = min(low[u], low[v]);
			if((p==-1&&child>1)||(p!=-1&&low[v]>=disc[u]))
			{
				isart[u] = 1; bicon.pb(vector<ii>());
				while(!st.empty()&&st.top()!=mp(u,v))
				{
					bicon.back().pb(st.top()); st.pop();
				}
				bicon.back().pb(st.top()); st.pop();
			}
		}
		else if(disc[v]<disc[u])
		{
			low[u] = min(low[u], disc[v]);
			st.push(mp(u,v));
		}
	}
}

ll dp[511211];
ll vis[511511];
ll cc; vi C;
ll tot[511511];
ll par[515115];
void prep_tree(ll u, ll p)
{
	C.pb(u); cc+=siz[u]; par[u]=p;
	dp[u] = siz[u]; vis[u]=1;
	for(ll v:tree[u])
	{
		if(v==p) continue;
		prep_tree(v,u);
		dp[u]+=dp[v];
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m; //do for each cc
	for(ll i=0;i<m;i++)
	{
		ll u,v; cin>>u>>v; u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}
	timer=1;
	for(ll i=0;i<n;i++)
	{
		if(!disc[i]) 
		{
			dfs(i,-1);
			if(!st.empty())
			{
				bicon.pb(vector<ii>());
				while(!st.empty())
				{
					bicon.back().pb(st.top()); st.pop();
				}
			}
		}
	}
	for(ll i=0;i<bicon.size();i++)
	{
		set<ll> S; set<ll> ss;
		for(ii v:bicon[i])
		{
			if(!isart[v.fi]) S.insert(v.fi);
			else ss.insert(v.fi);
			if(!isart[v.se]) S.insert(v.se);
			else ss.insert(v.se);
		}
		for(ll j:ss) 
		{
			tree[j].pb(n+i); tree[n+i].pb(j);
			//cerr<<"ADD EDGE "<<j<<' '<<n+i<<'\n';
		}
		//cerr<<"BICON "<<n+i<<' '<<S.size()<<'\n';
		siz[n+i] = ll(S.size()); //if cycle then alrdy +1
	}
	for(ll i=0;i<n;i++)
	{
		siz[i]=1;
	}
	for(ll i=0;i<n+bicon.size();i++)
	{
		if(!vis[i])
		{
			C.clear(); cc=0;
			prep_tree(i,-1);
			for(ll v:C)
			{
				tot[v] = cc;
			}
		}
	}
	ll ans = 0;
	for(ll i=0;i<n+bicon.size();i++)
	{
		if(i<n)
		{
			vi vec;
			for(ll j:tree[i])
			{
				ll v=dp[j];
				if(j==par[i])
				{
					v=tot[i]-dp[i];
				}
				vec.pb(v);
			}
			ll sos = 0; ll sum = 0;
			for(auto x:vec)
			{
				sos+=ll(x)*x;
				sum+=x;
			}
			ll res=0;
			res += sum*sum - sos;
			for(ll j:tree[i])
			{
				res += siz[j]*(siz[j]-1);
			}
			ans+=res;
			//cerr<<"ANS "<<i<<' '<<res<<'\n';
		}
		else
		{
			ll sz = siz[i]; ll res=0;
			res += sz*(sz-1)*(sz-2); //all 3 from here
			res += 2LL*sz*(sz-1)*(tot[i]-sz); //here-here-out
			vi vec; ll sm=0;
			ll neigh=0;
			for(ll j:tree[i])
			{
				neigh++;
				ll v=dp[j];
				if(j==par[i])
				{
					v=tot[i]-dp[i];
				}
				//cerr<<v<<' ';
				vec.pb(v);
				sm+=v;
			}
			//cerr<<'\n';
			assert(sm==tot[i]-sz);
			ll sos = 0; ll sum = 0;
			for(auto x:vec)
			{
				sos+=ll(x)*x;
				sum+=x;
			}
			res += sz*(sum*sum-sos);//out-here-out
			res += max(0LL,ll(neigh-2))*(sum*sum-sos);
			res += max(0LL,ll(neigh-1))*sz*2LL*sum;
			for(ll j:tree[i])
			{
				res += sz*siz[j]*(siz[j]-1);
			}
			//cerr<<"ANS "<<i<<' '<<res<<'\n';
			ans+=res;
		}
	}
	cout<<ans<<'\n';
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:98:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<bicon.size();i++)
             ~^~~~~~~~~~~~~
count_triplets.cpp:120:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<n+bicon.size();i++)
             ~^~~~~~~~~~~~~~~
count_triplets.cpp:133:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<n+bicon.size();i++)
             ~^~~~~~~~~~~~~~~

• 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