oj.uz

Submission #403998

# Submission time Handle Problem Language Result Execution time Memory
403998 2021-05-13T16:29:14 Z kshitij_sodani Duathlon (APIO18_duathlon) C++14
31 / 100
 156 ms 38120 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];
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));
		}
	}
}
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:pre[j]){
							if(ii!=j){
								llo co=ss.size();
								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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 30228 KB Output is correct
2 Correct 88 ms 31568 KB Output is correct
3 Correct 116 ms 31244 KB Output is correct
4 Correct 114 ms 32732 KB Output is correct
5 Correct 108 ms 27036 KB Output is correct
6 Correct 124 ms 29992 KB Output is correct
7 Correct 118 ms 28704 KB Output is correct
8 Correct 124 ms 29812 KB Output is correct
9 Correct 118 ms 27124 KB Output is correct
10 Correct 118 ms 27132 KB Output is correct
11 Correct 93 ms 23836 KB Output is correct
12 Correct 88 ms 23676 KB Output is correct
13 Correct 90 ms 23524 KB Output is correct
14 Correct 88 ms 23364 KB Output is correct
15 Correct 71 ms 22724 KB Output is correct
16 Correct 74 ms 22532 KB Output is correct
17 Correct 18 ms 16784 KB Output is correct
18 Correct 18 ms 16716 KB Output is correct
19 Correct 18 ms 16668 KB Output is correct
20 Correct 17 ms 16716 KB Output is correct
21 Correct 17 ms 16708 KB Output is correct
22 Correct 16 ms 16776 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9932 KB Output is correct
2 Correct 7 ms 9924 KB Output is correct
3 Correct 7 ms 9932 KB Output is correct
4 Correct 7 ms 9988 KB Output is correct
5 Correct 7 ms 9932 KB Output is correct
6 Correct 7 ms 9932 KB Output is correct
7 Correct 6 ms 9932 KB Output is correct
8 Correct 7 ms 9932 KB Output is correct
9 Correct 7 ms 9932 KB Output is correct
10 Correct 7 ms 9932 KB Output is correct
11 Correct 7 ms 9856 KB Output is correct
12 Correct 7 ms 9932 KB Output is correct
13 Correct 7 ms 9932 KB Output is correct
14 Correct 7 ms 9932 KB Output is correct
15 Correct 7 ms 9804 KB Output is correct
16 Correct 6 ms 9804 KB Output is correct
17 Correct 7 ms 9932 KB Output is correct
18 Correct 7 ms 9932 KB Output is correct
19 Correct 7 ms 9856 KB Output is correct
20 Correct 7 ms 9860 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 30580 KB Output is correct
2 Correct 150 ms 31796 KB Output is correct
3 Correct 146 ms 31972 KB Output is correct
4 Correct 136 ms 31896 KB Output is correct
5 Correct 139 ms 31924 KB Output is correct
6 Correct 155 ms 38120 KB Output is correct
7 Correct 139 ms 36144 KB Output is correct
8 Correct 146 ms 35124 KB Output is correct
9 Correct 141 ms 33940 KB Output is correct
10 Correct 135 ms 31548 KB Output is correct
11 Correct 156 ms 31804 KB Output is correct
12 Correct 140 ms 31376 KB Output is correct
13 Correct 137 ms 31256 KB Output is correct
14 Correct 120 ms 29812 KB Output is correct
15 Correct 110 ms 28476 KB Output is correct
16 Correct 73 ms 24388 KB Output is correct
17 Correct 136 ms 32108 KB Output is correct
18 Correct 125 ms 32104 KB Output is correct
19 Correct 125 ms 32012 KB Output is correct
20 Correct 127 ms 32048 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9932 KB Output is correct
2 Correct 8 ms 9932 KB Output is correct
3 Incorrect 7 ms 9804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 30564 KB Output is correct
2 Correct 133 ms 31752 KB Output is correct
3 Incorrect 136 ms 28176 KB Output isn't correct
4 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 -