oj.uz

Submission #790290

# Submission time Handle Problem Language Result Execution time Memory
790290 2023-07-22T14:14:03 Z Lyrically Duathlon (APIO18_duathlon) C++17
8 / 100
 1000 ms 13132 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);
}
vector<int> v[55][55];
int dis[55][55];
//can we go from i to j without touching k?
void calc()
{
	rep1(i,n)
	{
		dis[i][i]=0;
		rep1(j,n)
		{
			if(i!=j){dis[i][j]=(1LL<<60);}
		}
	}
	rep1(i,n)
	{
		for(auto v:edge[i])
		{
			dis[i][v]=dis[v][i]=1;
		}
	}
	rep1(k,n)
	{
		rep1(i,n)
		{
			rep1(j,n)
			{
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	rep1(i,n)
	{
		rep1(j,n)
		{
			if(i==j){continue;}
			v[i][j].pb(i);
			int fr=j;
			while(fr!=i)
			{
				for(auto vv:edge[fr])
				{
					if(dis[i][vv]+1==dis[i][fr])
					{
						v[i][j].pb(fr);
						fr=vv;break;
					}
				}
			}
			sort(v[i][j].begin(),v[i][j].end());
		}
	}
	int tot=0;
	rep1(i,n)
	{
		rep1(j,n)
		{
			if(i==j){continue;}
			rep1(k,n)
			{
				if(i==k||j==k){continue;}
				map<int,int> vis;
				for(auto x:v[i][k])
				{
					vis[x]++;
				}
				for(auto x:v[k][j])
				{
					vis[x]++;
				}
				vis[k]--;
				bool fl=1;
				for(auto x:vis)
				{
					if(x.second>=2){fl=0;}
				}
				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<=50){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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 5076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 5076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12056 KB Output is correct
2 Correct 35 ms 12180 KB Output is correct
3 Correct 42 ms 11900 KB Output is correct
4 Correct 35 ms 12360 KB Output is correct
5 Correct 39 ms 12080 KB Output is correct
6 Correct 35 ms 12164 KB Output is correct
7 Correct 34 ms 11936 KB Output is correct
8 Correct 35 ms 12128 KB Output is correct
9 Correct 35 ms 12168 KB Output is correct
10 Correct 35 ms 12104 KB Output is correct
11 Correct 38 ms 13132 KB Output is correct
12 Correct 36 ms 13012 KB Output is correct
13 Correct 41 ms 13004 KB Output is correct
14 Correct 35 ms 12760 KB Output is correct
15 Correct 29 ms 12480 KB Output is correct
16 Correct 28 ms 12352 KB Output is correct
17 Correct 7 ms 10068 KB Output is correct
18 Correct 7 ms 10196 KB Output is correct
19 Correct 8 ms 9956 KB Output is correct
20 Correct 7 ms 9940 KB Output is correct
21 Correct 7 ms 9812 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 3 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 38 ms 12712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 5076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 5076 KB Time limit exceeded
2 Halted 0 ms 0 KB -