Submission #72217

#	Time	Username	Problem	Language	Result	Execution time	Memory
72217		KLPP	Duathlon (APIO18_duathlon)	C++14	47 / 100	264 ms	35832 KiB

count_triplets

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;
typedef long long int lld;
lld DP[1000000];
bool visited[1000000];
vector<int>nei[1000000];
lld ans;
bool visited2[1000000];
void DFS(int node,lld dist){//cout<<node+1<<" "<<dist<<endl;
	visited[node]=true;
	lld sum=0;
	//lld square=0;
	//lld totaldist=0;
	for(int i=0;i<nei[node].size();i++){
		int v=nei[node][i];
		if(!visited[v]){
			DFS(v,dist+1);
			sum+=DP[v];
			//square+=DP[v]*DP[v];
		}
	}
	DP[node]=sum+1;
	//ans+=sum*sum-square;
	//cout<<sum*sum-square<<" "<<node+1<<endl;
	//ans+=dist*(dist-1);
}
void DFS2(int node,lld componentsize){
	visited2[node]=true;
	lld sq=componentsize-DP[node];
	sq*=sq;
	for(int i=0;i<nei[node].size();i++){
		int v=nei[node][i];
		if(!visited2[v]){
			DFS2(v,componentsize);
			sq+=DP[v]*DP[v];
		}		
	}
	ans+=(componentsize-1)*(componentsize-1)-sq;
	//cout<<(componentsize-1)*(componentsize-1)-sq<<" "<<node+1<<endl;
}
int main(){
	int n,m;
	cin>>n>>m;
	int edges[m][2];
	
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		x--;y--;
		edges[i][0]=x;
		edges[i][1]=y;
		nei[x].push_back(y);
		nei[y].push_back(x);
	}
	//for(int i=0;i<m;i++)cout<<edges[i][0]<<" "<<edges[i][1]<<endl;
	bool enter=true;
	for(int i=0;i<n;i++){
		if(nei[i].size()>2)enter=false;
	}
	if(enter){
	int component[n];
	
	for(int i=0;i<n;i++){
		component[i]=-1;
		
	}
	lld ans=0;
	int color=0;
	for(int i=0;i<n;i++){
		if(component[i]==-1){
			component[i]=color;
			
			queue<int>q;
			q.push(i);
			bool cycle=false;
			lld size=0;lld edges=0;
			while(!q.empty()){size++;
				int u=q.front();q.pop();
				//cout<<u<<" ";
				edges+=nei[u].size();
				for(int j=0;j<nei[u].size();j++){
					int v=nei[u][j];
					if(component[v]==-1){
						component[v]=color;
						q.push(v);
						
					}
				}
			}
			color++;//cout<<endl;
			/*for(int j=0;j<n;j++){
				if(component[j]==color-1)edges+=nei[j].size();
			}*/
			if(edges==2*size)cycle=true;
			//cout<<size<<" "<<cycle<<" "<<edges<<endl;
			
			if(cycle){
				ans+=(size*(size-1)*(size-2));
			}else{
				ans+=(size*(size-1)*(size-2))/3;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
	}
	if(n>50){
	ans=0;
	for(int i=0;i<n;i++){
		DP[i]=-1;
		visited[i]=false;
		visited2[i]=false;
	}
	for(int i=0;i<n;i++){
		if(!visited[i]){
			DFS(i,0);
			DFS2(i,DP[i]);
		}
	}//for(int i=0;i<n;i++)cout<<DP[i]<<" "<<i+1<<endl;
	cout<<ans<<endl;
	return 0;
	}
	if(n<=50){
	int component[n][n];
	vector<int>graph[n];
	for(int node=0;node<n;node++){
		for(int j=0;j<m;j++){
			if(edges[j][0]!=node && edges[j][1]!=node){//cout<<edges[j][0]<<" "<<edges[j][1]<<" "<<j<<endl;
				graph[edges[j][0]].push_back(edges[j][1]);
				graph[edges[j][1]].push_back(edges[j][0]);
				//cout<<edges[j][0]<<" "<<edges[j][1]<<" "<<j<<endl;
			}
		}
		int color=0;
		for(int i=0;i<n;i++)component[node][i]=-1;
		for(int i=0;i<n;i++){
			if(component[node][i]==-1){
				component[node][i]=color;
				queue<int>q;
				q.push(i);
				while(!q.empty()){
					int u=q.front();q.pop();
					//cout<<u<<" ";
					for(int j=0;j<graph[u].size();j++){
						int v=graph[u][j];
						if(component[node][v]==-1){
							component[node][v]=color;
							q.push(v);
						}
					}
				}
				color++;//cout<<endl;
			}
		}
		for(int i=0;i<n;i++)graph[i].clear();
	}
	int cnt=0;
	for(int s=0;s<n;s++){
		for(int f=0;f<n;f++){
			for(int c=0;c<n;c++){
				if(s!=c && s!=f && f!=c){
					bool b=true;
					for(int i=0;i<n;i++){
						if(i!=c){
						if(component[i][c]!=component[i][s] && component[i][c]!=component[i][f]){
							b=false;
						}
						}
					}cnt+=b;
				}
			}
		}
	}
	cout<<cnt<<endl;
	
	return 0;	
	}
}

Compilation message (stderr)

count_triplets.cpp: In function 'void DFS(int, lld)':
count_triplets.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<nei[node].size();i++){
              ~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void DFS2(int, lld)':
count_triplets.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<nei[node].size();i++){
              ~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:86:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<nei[u].size();j++){
                 ~^~~~~~~~~~~~~~
count_triplets.cpp:149:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j=0;j<graph[u].size();j++){
                  ~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10