Submission #408083

#	Time	Username	Problem	Language	Result	Execution time	Memory
408083		juggernaut	Duathlon (APIO18_duathlon)	C++17	8 / 100	102 ms	10516 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
int n,m;
vector<int>g[100005];
ll ans;
bool circle;
bool vis[100005];
int sz;
void dfs(int v,int p){
	vis[v]=true;
	sz++;
	for(int to:g[v])if(to!=p){
		if(vis[to]){
			circle=true;
			continue;
		}
		dfs(to,v);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++)if(!vis[i]){
		circle=false;
		sz=0;
		dfs(i,i);
		ll s=sz*1ll;
		if(circle)ans+=s*(s-1)*(s-2);
		else for(int i=1;i<=sz;i++)ans+=2ll*(i-1)*(1ll*(sz-i));
	}
	printf("%lld",ans);
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

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