Submission #50345

#	Time	Username	Problem	Language	Result	Execution time	Memory
50345		zscoder	Duathlon (APIO18_duathlon)	C++17	90 / 100	297 ms	53548 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

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

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

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

void dfs(int u, int p)
{
	disc[u]=++timer; int child=0; low[u]=disc[u];
	for(int 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));
		}
	}
}

int dp[511211];
int vis[511511];
int cc; vi C;
int tot[511511];
int par[515115];
void prep_tree(int u, int p)
{
	C.pb(u); cc+=siz[u]; par[u]=p;
	dp[u] = siz[u]; vis[u]=1;
	for(int 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(int i=0;i<m;i++)
	{
		int u,v; cin>>u>>v; u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}
	timer=1;
	for(int 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(int i=0;i<bicon.size();i++)
	{
		set<int> S; set<int> 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(int 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] = int(S.size()); //if cycle then alrdy +1
	}
	for(int i=0;i<n;i++)
	{
		siz[i]=1;
	}
	for(int i=0;i<n+bicon.size();i++)
	{
		if(!vis[i])
		{
			C.clear(); cc=0;
			prep_tree(i,-1);
			for(int v:C)
			{
				tot[v] = cc;
			}
		}
	}
	ll ans = 0;
	for(int i=0;i<n+bicon.size();i++)
	{
		if(i<n)
		{
			vi vec;
			for(int j:tree[i])
			{
				int 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(int 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; int sm=0;
			int neigh=0;
			for(int j:tree[i])
			{
				neigh++;
				int 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(int 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:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<bicon.size();i++)
              ~^~~~~~~~~~~~~
count_triplets.cpp:120:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<n+bicon.size();i++)
              ~^~~~~~~~~~~~~~~
count_triplets.cpp:133:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int 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: 0 / 10