Submission #790308

#	Time	Username	Problem	Language	Result	Execution time	Memory
790308		Lyrically	Duathlon (APIO18_duathlon)	C++17	13 / 100	194 ms	12036 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()
{
	rep1(i,n)
	{
		Set[Find(i)].pb(i);
	}
	rep1(i,n)
	{
		for(auto v:edge[i])
		{
			if(i>=v){continue;}
			E[Find(i)]++;
		}
	}
	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);
}
bool dp[15][15][(1<<10)+5];
bool e[15][15];
void dfs(int st,int x,int msk)
{
	if(dp[st][x][msk]){return;}
	dp[st][x][msk]=1;
	for(int i:edge[x])
	{
		if(msk&(1<<(i-1))){continue;}
		dfs(st,i,msk|(1<<(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,(1<<(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;
				rep(x,(1<<n))
				{
					if(!((x&(1<<(i-1)))&&(x&(1<<(k-1))))){continue;}
					rep(y,(1<<n))
					{
						if(!((y&(1<<(k-1)))&&(y&(1<<(j-1))))){continue;}
						if(dp[i][k][x]&&dp[k][j][y])
						{
							if(!((x-(1<<(k-1)))&y))
							{
								fl=1;break;
							}
						}
					}
				}
				tot+=fl;
			}
		}
	}
	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]++;
	}
	bool f=1;
	rep1(i,n){f&=(deg[i]<=2);}
	if(f){work();return 0;}
	if(n<=10){calc();return 0;}
	rep1(i,n)
	{
		Set[Find(i)].pb(i);
	}
	rep1(i,n)
	{
		for(auto v:edge[i])
		{
			if(i>=v){continue;}
			E[Find(i)]++;
		}
	}
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void work()':
count_triplets.cpp:42: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]
   42 |    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: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 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