Submission #265014

#	Time	Username	Problem	Language	Result	Execution time	Memory
265014		dsjong	Duathlon (APIO18_duathlon)	C++14	31 / 100	91 ms	13168 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
vector<int>adj[100005];
bool vis[100005];
long long cnt=0;
bool bb=true;
int des[100005];
int par[100005];
vector<int>v;
void dfs(int i){
	v.push_back(i);
	if(adj[i].size()==1) bb=false;
	cnt++;
	vis[i]=true;
	for(int j:adj[i]){
		if(!vis[j]){
			par[j]=i;
			dfs(j);
			des[i]+=des[j];
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		par[i]=0;
		des[i]=1;
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			cnt=0;
			v.clear();
			bb=true;
			dfs(i);
			if(bb) ans=ans+((long long)(cnt)*(cnt-1)*(cnt-2));
			else{
				long long res=0;
				for(int j:v){
					for(int k:adj[j]){
						if(k==par[j]){
							res+=(cnt-des[j])*(cnt-des[j]);
						}
						else{
							res+=((long long)des[k])*des[k];
						}
						//cout<<res<<" ";
					}
				}
				ans=ans+cnt*(cnt-1)*(cnt-1)-res;
				//ans=ans+((long long)(cnt)*(cnt-1)*(cnt-2)/3);
			}
		}
	}
	cout<<ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 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