oj.uz

Submission #790308

# Submission time Handle Problem Language Result Execution time Memory
790308 2023-07-22T14:28:33 Z Lyrically Duathlon (APIO18_duathlon) C++17
13 / 100
 194 ms 12036 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()
{
	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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5000 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5016 KB Output is correct
7 Correct 179 ms 5136 KB Output is correct
8 Correct 174 ms 5076 KB Output is correct
9 Correct 142 ms 5148 KB Output is correct
10 Correct 110 ms 5140 KB Output is correct
11 Correct 180 ms 5076 KB Output is correct
12 Correct 183 ms 5132 KB Output is correct
13 Correct 176 ms 5144 KB Output is correct
14 Correct 182 ms 5132 KB Output is correct
15 Correct 194 ms 5136 KB Output is correct
16 Correct 186 ms 5132 KB Output is correct
17 Correct 185 ms 5144 KB Output is correct
18 Correct 182 ms 5132 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 5012 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 178 ms 5076 KB Output is correct
23 Correct 34 ms 5076 KB Output is correct
24 Correct 9 ms 5076 KB Output is correct
25 Correct 36 ms 5016 KB Output is correct
26 Correct 181 ms 5136 KB Output is correct
27 Correct 10 ms 5076 KB Output is correct
28 Correct 34 ms 5112 KB Output is correct
29 Correct 180 ms 5076 KB Output is correct
30 Correct 10 ms 5116 KB Output is correct
31 Correct 41 ms 5012 KB Output is correct
32 Correct 183 ms 5144 KB Output is correct
33 Correct 12 ms 5076 KB Output is correct
34 Correct 2 ms 4948 KB Output is correct
35 Correct 3 ms 4948 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5000 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5016 KB Output is correct
7 Correct 179 ms 5136 KB Output is correct
8 Correct 174 ms 5076 KB Output is correct
9 Correct 142 ms 5148 KB Output is correct
10 Correct 110 ms 5140 KB Output is correct
11 Correct 180 ms 5076 KB Output is correct
12 Correct 183 ms 5132 KB Output is correct
13 Correct 176 ms 5144 KB Output is correct
14 Correct 182 ms 5132 KB Output is correct
15 Correct 194 ms 5136 KB Output is correct
16 Correct 186 ms 5132 KB Output is correct
17 Correct 185 ms 5144 KB Output is correct
18 Correct 182 ms 5132 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 5012 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 178 ms 5076 KB Output is correct
23 Correct 34 ms 5076 KB Output is correct
24 Correct 9 ms 5076 KB Output is correct
25 Correct 36 ms 5016 KB Output is correct
26 Correct 181 ms 5136 KB Output is correct
27 Correct 10 ms 5076 KB Output is correct
28 Correct 34 ms 5112 KB Output is correct
29 Correct 180 ms 5076 KB Output is correct
30 Correct 10 ms 5116 KB Output is correct
31 Correct 41 ms 5012 KB Output is correct
32 Correct 183 ms 5144 KB Output is correct
33 Correct 12 ms 5076 KB Output is correct
34 Correct 2 ms 4948 KB Output is correct
35 Correct 3 ms 4948 KB Output is correct
36 Correct 2 ms 4948 KB Output is correct
37 Incorrect 3 ms 5016 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 10836 KB Output is correct
2 Correct 34 ms 10824 KB Output is correct
3 Correct 39 ms 10568 KB Output is correct
4 Correct 34 ms 11060 KB Output is correct
5 Correct 34 ms 10804 KB Output is correct
6 Correct 40 ms 10764 KB Output is correct
7 Correct 33 ms 10512 KB Output is correct
8 Correct 42 ms 10840 KB Output is correct
9 Correct 35 ms 10940 KB Output is correct
10 Correct 35 ms 10712 KB Output is correct
11 Correct 41 ms 12036 KB Output is correct
12 Correct 40 ms 11840 KB Output is correct
13 Correct 35 ms 11996 KB Output is correct
14 Correct 52 ms 11796 KB Output is correct
15 Correct 31 ms 11704 KB Output is correct
16 Correct 32 ms 11624 KB Output is correct
17 Correct 7 ms 10068 KB Output is correct
18 Correct 7 ms 10068 KB Output is correct
19 Correct 9 ms 9940 KB Output is correct
20 Correct 7 ms 9916 KB Output is correct
21 Correct 7 ms 9684 KB Output is correct
22 Correct 7 ms 9684 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 11436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 11440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5000 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5016 KB Output is correct
7 Correct 179 ms 5136 KB Output is correct
8 Correct 174 ms 5076 KB Output is correct
9 Correct 142 ms 5148 KB Output is correct
10 Correct 110 ms 5140 KB Output is correct
11 Correct 180 ms 5076 KB Output is correct
12 Correct 183 ms 5132 KB Output is correct
13 Correct 176 ms 5144 KB Output is correct
14 Correct 182 ms 5132 KB Output is correct
15 Correct 194 ms 5136 KB Output is correct
16 Correct 186 ms 5132 KB Output is correct
17 Correct 185 ms 5144 KB Output is correct
18 Correct 182 ms 5132 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 5012 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 178 ms 5076 KB Output is correct
23 Correct 34 ms 5076 KB Output is correct
24 Correct 9 ms 5076 KB Output is correct
25 Correct 36 ms 5016 KB Output is correct
26 Correct 181 ms 5136 KB Output is correct
27 Correct 10 ms 5076 KB Output is correct
28 Correct 34 ms 5112 KB Output is correct
29 Correct 180 ms 5076 KB Output is correct
30 Correct 10 ms 5116 KB Output is correct
31 Correct 41 ms 5012 KB Output is correct
32 Correct 183 ms 5144 KB Output is correct
33 Correct 12 ms 5076 KB Output is correct
34 Correct 2 ms 4948 KB Output is correct
35 Correct 3 ms 4948 KB Output is correct
36 Correct 2 ms 4948 KB Output is correct
37 Incorrect 3 ms 5016 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5000 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5016 KB Output is correct
7 Correct 179 ms 5136 KB Output is correct
8 Correct 174 ms 5076 KB Output is correct
9 Correct 142 ms 5148 KB Output is correct
10 Correct 110 ms 5140 KB Output is correct
11 Correct 180 ms 5076 KB Output is correct
12 Correct 183 ms 5132 KB Output is correct
13 Correct 176 ms 5144 KB Output is correct
14 Correct 182 ms 5132 KB Output is correct
15 Correct 194 ms 5136 KB Output is correct
16 Correct 186 ms 5132 KB Output is correct
17 Correct 185 ms 5144 KB Output is correct
18 Correct 182 ms 5132 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 5012 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 178 ms 5076 KB Output is correct
23 Correct 34 ms 5076 KB Output is correct
24 Correct 9 ms 5076 KB Output is correct
25 Correct 36 ms 5016 KB Output is correct
26 Correct 181 ms 5136 KB Output is correct
27 Correct 10 ms 5076 KB Output is correct
28 Correct 34 ms 5112 KB Output is correct
29 Correct 180 ms 5076 KB Output is correct
30 Correct 10 ms 5116 KB Output is correct
31 Correct 41 ms 5012 KB Output is correct
32 Correct 183 ms 5144 KB Output is correct
33 Correct 12 ms 5076 KB Output is correct
34 Correct 2 ms 4948 KB Output is correct
35 Correct 3 ms 4948 KB Output is correct
36 Correct 2 ms 4948 KB Output is correct
37 Incorrect 3 ms 5016 KB Output isn't correct
38 Halted 0 ms 0 KB -