제출 #404347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
404347		kshitij_sodani	철인 이종 경기 (APIO18_duathlon)	C++14	71 / 100	1130 ms	988420 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];
vector<llo> adj3[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 ok=0;
void dfs3(int no){
	vis[no]=1;
	/*if(ok){
		cout<<no<<'?'<<vis[no]<<endl;
	}*/
	for(auto j:adj3[no]){
		/*if(ok==1){
			cout<<no<<",,"<<j<<"::"<<vis[j]<<endl;
		}*/
		//dfs3(j);
		if(vis[j]==0){
			/*if(ok==1){
				cout<<no<<",,"<<j<<"::"<<vis[j]<<endl;
				dfs3(j);
			}*/
			dfs3(j);
			//if(ok==1){
			//	cout<<no<<",,"<<j<<"::"<<vis[j]<<endl;
			//}
		}
	}
}
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);
	}
	if(n<=10){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				for(int k=0;k<n;k++){
					if(i==j or i==k or j==k){
						continue;
					}
					for(int ii=0;ii<(1<<n);ii++){
						int aa=ii;
						int bb=(1<<n)-1-aa;
						if(aa&(1<<j)){
							bb+=(1<<j);
						}
						else{
							aa+=(1<<j);
						}
						for(int mm=0;mm<n;mm++){
							adj3[mm].clear();
							vis[mm]=0;
						}
						for(int mm=0;mm<n;mm++){
							for(auto jj:adj[mm]){
								
								if(((1<<mm)&aa) and ((1<<jj)&aa)){
									/*if(i==0 and j==1 and k==2 and ii==3){
										cout<<mm<<","<<jj<<endl;
									}*/
									adj3[mm].pb(jj);
								}
							}
						}
						//for(int )
						
						dfs3(i);
						
						if(vis[j]){
							for(int mm=0;mm<n;mm++){
								adj3[mm].clear();
								vis[mm]=0;
							}
							for(int mm=0;mm<n;mm++){
								for(auto jj:adj[mm]){
									if(((1<<mm)&bb) and ((1<<jj)&bb)){
										adj3[mm].pb(jj);
									}
								}
							}
							dfs3(j);
							if(vis[k]){
								ans++;
								break;
							}
						}

					}
				}
			}
		}
		cout<<ans<<endl;
		return 0;
	}
	
	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+=(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;
}
 

컴파일 시 표준 에러 (stderr) 메시지

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

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