Submission #790327

#	Time	Username	Problem	Language	Result	Execution time	Memory
790327		Lyrically	Duathlon (APIO18_duathlon)	C++17	0 / 100	57 ms	19664 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
int read(){int x;scanf("%lld",&x);return x;}
void print(int x){printf("%lld\n",x);}
void file(string s)
{
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
const int mod=998244353;
int n,m;
vector<int> edge[100005];
int deg[100005];
int Fa[100005];
vector<int> Set[100005];
int E[100005];
int Find(int x){return Fa[x]==x?x:Fa[x]=Find(Fa[x]);}
void work()
{
	int res=0;
	rep1(i,n)
	{
		if(!Set[i].empty())
		{
			if(E[i]==Set[i].size())
			{
				res+=E[i]*(E[i]-1)*(E[i]-2);
			}
			else
			{
				res+=(E[i]+1)*E[i]*(E[i]-1)/3;
			}
		}
	}
	print(res);
}
unordered_map<int,int> dpp[55][55];
bool e[55][55];
void dfs(int st,int x,int msk)
{
	if(dpp[st][x].count(msk)){return;}
	dpp[st][x][msk]=1;
	for(int i:edge[x])
	{
		if(msk&(1ll<<(i-1))){continue;}
		dfs(st,i,msk|(1ll<<(i-1)));
	}
}
//can we go from i to j with the path msk?
void calc()
{
	rep1(i,n)
	{
		for(int v:edge[i])
		{
			e[i][v]=e[v][i]=1;
		}
	}
	rep1(i,n)
	{
		dfs(i,i,(1ll<<(i-1)));
	}
	int tot=0;
	rep1(i,n)
	{
		rep1(j,n)
		{
			if(i==j){continue;}
			if(Find(i)!=Find(j)){continue;}
			rep1(k,n)
			{
				if(i==k||j==k){continue;}
				if(Find(i)!=Find(k)){continue;}
				bool fl=0;
				for(auto it:dpp[i][k])
				{
					for(auto nit:dpp[k][j])
					{
						int x=it.first,y=nit.first;
						if(!((x-(1ll<<(k-1)))&y))
						{
							fl=1;break;
						}
					}
				}
				tot+=fl;
			}
		}
	}
	print(tot);
}
bool vis[100005];
int res[100005];
int cnt[100005];
void dfs(int x,int fa)
{
	cnt[x]=1;
	for(int v:edge[x])
	{
		if(v==fa){continue;}
		dfs(v,x);
		cnt[x]+=cnt[v];
		res[x]+=res[v]+cnt[v];
	}
}
void dfs2(int x,int fa)
{
	for(int v:edge[x])
	{
		if(v==fa){continue;}
		res[v]=n-cnt[v]+res[x]-cnt[v];
		dfs2(v,x);
	}
}
void solve()
{
	int tot=0;
	rep1(i,n)
	{
		if(Set[i].empty()){continue;}
		dfs(i,0);
		/*
		for(auto v:Set[i])
		{
			cout<<v<<" "<<cnt[v]<<" "<<res[v]<<endl;
		}*/
		dfs2(i,0);
		/*
		for(auto v:Set[i])
		{
			cout<<v<<" "<<cnt[v]<<" "<<res[v]<<endl;
		}*/
		for(auto v:Set[i])
		{
			tot+=res[v]-n+1;
		}
	}
	print(tot);
}
signed main()
{
	n=read(),m=read();rep1(i,n){Fa[i]=i;}
	rep1(i,m)
	{
		int u=read(),v=read();Fa[Find(u)]=Find(v);
		edge[u].pb(v),edge[v].pb(u);
		deg[u]++,deg[v]++;
	}
	rep1(i,n)
	{
		Set[Find(i)].pb(i);
	}
	rep1(i,n)
	{
		for(auto v:edge[i])
		{
			if(i>=v){continue;}
			E[Find(i)]++;
		}
	}
	bool fl=1;
	rep1(i,n)
	{
		if(Set[i].empty()){continue;}
		if(E[i]==(int)Set[i].size()-1){continue;}
		fl=0;
	}
	if(fl){solve();return 0;}
	bool f=1;
	rep1(i,n){f&=(deg[i]<=2);}
	if(f){work();return 0;}
	if(n<=10){calc();return 0;}
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void work()':
count_triplets.cpp:30:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    if(E[i]==Set[i].size())
      |       ~~~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'long long int read()':
count_triplets.cpp:8:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | int read(){int x;scanf("%lld",&x);return x;}
      |                  ~~~~~^~~~~~~~~~~
count_triplets.cpp: In function 'void file(std::string)':
count_triplets.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((s+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((s+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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