Submission #404329

#	Time	Username	Problem	Language	Result	Execution time	Memory
404329		kshitij_sodani	Duathlon (APIO18_duathlon)	C++14	10 / 100	1095 ms	41384 KiB

count_triplets

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n,m;
vector<llo> adj[100001];
llo vis[100001];
llo par[100001];
llo ind[100001];
vector<llo> ss;
set<llo> adj2[100001];
llo val[100001];
vector<llo> pre[100001];
llo par5[100001];
llo lev[100001];
void dfs(llo no,llo par2=-1,llo levv=0){
	ss.pb(no);
	vis[no]=1;
	par5[no]=par2;
	par[no]=no;
	lev[no]=levv;
	for(auto j:adj[no]){
		if(j!=par2){
			if(vis[j]==0){
				dfs(j,no,levv+1);
			}
			else if(lev[j]<lev[no]){
				vector<llo> cot;
				llo cur=no;
				while(cur!=j){
					cot.pb(cur);
					cur=par5[cur];
				}
				cot.pb(cur);
				for(auto ii:cot){
					par[ii]=j;
				}
			}
		}
	}
}
llo par3[100001];
llo ans=0;
void dfs2(llo no,llo par2=-1){
	par3[no]=par2;
	//val[no]=1;
	//ss.pb(no);
//	vis[no]=1;
	llo su=0;
	for(auto j:adj2[no]){
		if(j!=par2){
			dfs2(j,no);
			su+=val[j];
			val[no]+=val[j];
		}
	}
	for(auto j:adj2[no]){
		if(j!=par2){
			//cout<<no<<":"<<j<<":"<<(val[j]*(su-val[j])*(val[no]-su))<<endl;
			//ans+=(val[j]*(su-val[j])*(val[no]-su));
		}
	}
}
llo pa=-1;
llo co5=0;
llo vis2[100001];
void dfs3(llo no){
	vis2[no]=1;
	co5++;
	for(auto j:adj[no]){
		if(vis2[j]==0 and par[j]!=pa){
			dfs3(j);
		}
	}


}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(llo i=0;i<m;i++){
		llo aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
	}
	
	for(llo i=0;i<n;i++){
		if(vis[i]==0){
			ss.clear();
			//dfs2(i);
		/*	for(auto j:ss){
				ans+=2*(val[j]-1)*(ss.size()-val[j]);
				//cout<<j<<":";
			}*/
			//cout<<endl;
			//continue;
			dfs(i);
			for(auto j:ss){
				val[par[j]]++;
				for(auto ii:adj[j]){
					if(par[j]!=par[ii]){
						adj2[par[j]].insert(par[ii]);
					}
				}
			}
			
			//continue;
			for(auto j:ss){
				pre[par[j]].pb(j);
			}
			dfs2(i);
			/*for(auto j:ss){
				cout<<j<<":"<<par[j]<<":"<<val[j]<<endl;
			}*/
			llo nn=ss.size();
			for(auto j:ss){
				
				if(par[j]==j){

					llo aa=pre[j].size();
					if(aa>=3){
						ans+=((((aa*(aa-1)*(aa-2)))));
					}
					//ans+=2*(val[j]-aa)*aa*(nn-val[j]);

					//continue;
					llo co2=0;
					//if(aa>=2){
						for(auto ii:ss){
							vis2[ii]=0;		
						}
						vector<pair<llo,vector<llo>>> cal;
						for(auto ii:pre[j]){
						//	pa=par[ii];
						//	co5=0;
						//	dfs3(ii);
//
							//ans+=2*((co5-1)*(aa-1)*(aa-1));
						//	cout<<ii<<":"<<co5<<endl;
						//	if(ii!=j){
							vector<llo> pp;

								for(auto k:adj[ii]){
									if(par[k]!=par[ii]){
										if(k!=par5[ii]){
											//co-=val[k];
											//co2+=val[k];
											pp.pb(val[par[k]]);
											//cout<<ii<<":"<<k<<":"<<val[k]*(nn-aa-val[k])<<endl;
											//ans+=val[k]*(nn-aa-val[k])*2;
										}
										else{
											pp.pb(nn-val[par[ii]]);
										}
									}

								}

							cal.pb({ii,pp});
						}
						for(auto ii2:cal){
							llo su=0;
							for(auto jj:ii2.b){
								su+=jj;
							}
							//cout<<ii2.a<<endl;
							llo su9=0;
							for(auto jj:ii2.b){
								//cout<<jj<<"<";
								ans+=2*(nn-su-aa)*jj*aa;
								if(aa>=3){
									ans+=jj*(aa-1)*(aa-2)*2;
								}		
								ans+=(aa-1)*jj*2;
								ans+=su9*jj*2;
								su9+=jj;
							}
						//	cout<<endl;
						}
						
					//}
				}
			}



		}
	}
	cout<<ans<<endl;
//	dfs(0);








	return 0;
}
 

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:136:10: warning: unused variable 'co2' [-Wunused-variable]
  136 |      llo co2=0;
      |          ^~~

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