oj.uz

Submission #790327

# Submission time Handle Problem Language Result Execution time Memory
790327 2023-07-22T14:45:32 Z Lyrically Duathlon (APIO18_duathlon) C++17
0 / 100
 57 ms 19664 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 2 ms 5184 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Incorrect 3 ms 5184 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 2 ms 5184 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Incorrect 3 ms 5184 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 11028 KB Output is correct
2 Correct 35 ms 12280 KB Output is correct
3 Correct 35 ms 12096 KB Output is correct
4 Correct 37 ms 12488 KB Output is correct
5 Correct 50 ms 12184 KB Output is correct
6 Correct 34 ms 12228 KB Output is correct
7 Correct 44 ms 12036 KB Output is correct
8 Correct 34 ms 12232 KB Output is correct
9 Correct 34 ms 12264 KB Output is correct
10 Correct 34 ms 12124 KB Output is correct
11 Correct 36 ms 13188 KB Output is correct
12 Correct 36 ms 13000 KB Output is correct
13 Correct 35 ms 13060 KB Output is correct
14 Correct 34 ms 12876 KB Output is correct
15 Correct 31 ms 12556 KB Output is correct
16 Correct 31 ms 12516 KB Output is correct
17 Incorrect 9 ms 11604 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 2 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Incorrect 3 ms 5204 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 12848 KB Output is correct
2 Correct 43 ms 12940 KB Output is correct
3 Correct 43 ms 12860 KB Output is correct
4 Correct 43 ms 12880 KB Output is correct
5 Correct 43 ms 12872 KB Output is correct
6 Correct 57 ms 19664 KB Output is correct
7 Correct 50 ms 16752 KB Output is correct
8 Correct 46 ms 16456 KB Output is correct
9 Correct 54 ms 14720 KB Output is correct
10 Incorrect 44 ms 12944 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Incorrect 3 ms 5188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 12864 KB Output is correct
2 Correct 44 ms 12784 KB Output is correct
3 Incorrect 43 ms 13332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 2 ms 5184 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Incorrect 3 ms 5184 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 2 ms 5184 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Incorrect 3 ms 5184 KB Output isn't correct
7 Halted 0 ms 0 KB -