oj.uz

Submission #403987

# Submission time Handle Problem Language Result Execution time Memory
403987 2021-05-13T16:19:01 Z kshitij_sodani Duathlon (APIO18_duathlon) C++14
0 / 100
 150 ms 31856 KB 
//#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];

void dfs(llo no,llo par2=-1){
	ss.pb(no);
	vis[no]=1;
	par5[no]=par2;
	par[no]=no;
	for(auto j:adj[no]){
		if(j!=par2){
			if(vis[j]==0){
				dfs(j,no);
			}
			else if(par[j]!=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];
void dfs2(llo no,llo par2=-1){
	par3[no]=par2;
	for(auto j:adj2[no]){
		if(j!=par2){
			dfs2(j,no);
			val[no]+=val[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);
	}
	llo ans=0;
	for(llo i=0;i<n;i++){
		if(vis[i]==0){
			ss.clear();
			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]);
					}
				}
			}
			dfs2(i);
			//continue;
			for(auto j:ss){
				pre[par[j]].pb(j);
			}
			/*for(auto j:ss){
				cout<<j<<":"<<par[j]<<":"<<val[j]<<endl;
			}*/
			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*(n-val[j]);
					llo co2=0;
					if(aa>=2){
						for(auto ii:pre[j]){
							if(ii!=j){
								llo co=n;
								co-=aa;
								for(auto k:adj[ii]){
									if(k!=par5[ii]){
										co-=val[k];
										co2+=val[k];
									}
								}
								ans+=2*(aa-1)*co;
							}
						}
						ans+=2*(aa-1)*co2;
					}
				}
			}



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








	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 31460 KB Output is correct
2 Correct 88 ms 31480 KB Output is correct
3 Incorrect 110 ms 31204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 31856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 31796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -