oj.uz

Submission #790293

# Submission time Handle Problem Language Result Execution time Memory
790293 2023-07-22T14:15:14 Z Lyrically Duathlon (APIO18_duathlon) C++17
8 / 100
 45 ms 12024 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;}
			if(Find(i)!=Find(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;}
			if(Find(i)!=Find(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 Incorrect 2 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10832 KB Output is correct
2 Correct 36 ms 10872 KB Output is correct
3 Correct 34 ms 10680 KB Output is correct
4 Correct 34 ms 11112 KB Output is correct
5 Correct 33 ms 10932 KB Output is correct
6 Correct 34 ms 10884 KB Output is correct
7 Correct 37 ms 10600 KB Output is correct
8 Correct 42 ms 10876 KB Output is correct
9 Correct 34 ms 10996 KB Output is correct
10 Correct 33 ms 10840 KB Output is correct
11 Correct 37 ms 12024 KB Output is correct
12 Correct 35 ms 11860 KB Output is correct
13 Correct 34 ms 11992 KB Output is correct
14 Correct 34 ms 11892 KB Output is correct
15 Correct 28 ms 11720 KB Output is correct
16 Correct 29 ms 11700 KB Output is correct
17 Correct 7 ms 10172 KB Output is correct
18 Correct 7 ms 10196 KB Output is correct
19 Correct 8 ms 10040 KB Output is correct
20 Correct 7 ms 9940 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 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 39 ms 11460 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 45 ms 11456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
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 -