oj.uz

Submission #404336

# Submission time Handle Problem Language Result Execution time Memory
404336 2021-05-14T08:25:25 Z kshitij_sodani Duathlon (APIO18_duathlon) C++14
66 / 100
 225 ms 40284 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];
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+=(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

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.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 97 ms 39672 KB Output is correct
2 Correct 97 ms 39748 KB Output is correct
3 Correct 143 ms 32676 KB Output is correct
4 Correct 127 ms 40284 KB Output is correct
5 Correct 131 ms 28496 KB Output is correct
6 Correct 167 ms 31824 KB Output is correct
7 Correct 163 ms 30848 KB Output is correct
8 Correct 156 ms 32388 KB Output is correct
9 Correct 147 ms 27556 KB Output is correct
10 Correct 162 ms 27780 KB Output is correct
11 Correct 105 ms 23968 KB Output is correct
12 Correct 104 ms 24004 KB Output is correct
13 Correct 110 ms 23996 KB Output is correct
14 Correct 95 ms 23620 KB Output is correct
15 Correct 83 ms 23340 KB Output is correct
16 Correct 101 ms 23004 KB Output is correct
17 Correct 22 ms 17572 KB Output is correct
18 Correct 23 ms 17492 KB Output is correct
19 Correct 23 ms 17484 KB Output is correct
20 Correct 23 ms 17476 KB Output is correct
21 Correct 22 ms 17556 KB Output is correct
22 Correct 24 ms 17528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9868 KB Output is correct
2 Correct 8 ms 9872 KB Output is correct
3 Correct 7 ms 9892 KB Output is correct
4 Correct 7 ms 10060 KB Output is correct
5 Correct 7 ms 10060 KB Output is correct
6 Correct 7 ms 9932 KB Output is correct
7 Correct 7 ms 9932 KB Output is correct
8 Correct 7 ms 9996 KB Output is correct
9 Correct 7 ms 9932 KB Output is correct
10 Correct 8 ms 9868 KB Output is correct
11 Correct 7 ms 9932 KB Output is correct
12 Correct 7 ms 9864 KB Output is correct
13 Correct 9 ms 9932 KB Output is correct
14 Correct 8 ms 9932 KB Output is correct
15 Correct 8 ms 9856 KB Output is correct
16 Correct 7 ms 9804 KB Output is correct
17 Correct 8 ms 9980 KB Output is correct
18 Correct 8 ms 9932 KB Output is correct
19 Correct 7 ms 9928 KB Output is correct
20 Correct 7 ms 9944 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 31840 KB Output is correct
2 Correct 207 ms 31996 KB Output is correct
3 Correct 184 ms 31924 KB Output is correct
4 Correct 174 ms 31868 KB Output is correct
5 Correct 188 ms 31912 KB Output is correct
6 Correct 193 ms 39864 KB Output is correct
7 Correct 195 ms 37424 KB Output is correct
8 Correct 214 ms 35980 KB Output is correct
9 Correct 202 ms 34520 KB Output is correct
10 Correct 202 ms 31652 KB Output is correct
11 Correct 200 ms 31796 KB Output is correct
12 Correct 200 ms 31408 KB Output is correct
13 Correct 209 ms 31284 KB Output is correct
14 Correct 153 ms 29960 KB Output is correct
15 Correct 152 ms 28768 KB Output is correct
16 Correct 99 ms 25168 KB Output is correct
17 Correct 159 ms 33848 KB Output is correct
18 Correct 161 ms 33068 KB Output is correct
19 Correct 155 ms 32868 KB Output is correct
20 Correct 166 ms 32524 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9868 KB Output is correct
2 Correct 9 ms 9928 KB Output is correct
3 Correct 8 ms 9864 KB Output is correct
4 Correct 7 ms 9872 KB Output is correct
5 Correct 7 ms 9804 KB Output is correct
6 Correct 8 ms 9804 KB Output is correct
7 Correct 7 ms 9804 KB Output is correct
8 Correct 7 ms 9804 KB Output is correct
9 Correct 7 ms 9864 KB Output is correct
10 Correct 8 ms 9804 KB Output is correct
11 Correct 8 ms 9804 KB Output is correct
12 Correct 8 ms 10004 KB Output is correct
13 Correct 7 ms 9932 KB Output is correct
14 Correct 7 ms 9872 KB Output is correct
15 Correct 8 ms 9960 KB Output is correct
16 Correct 8 ms 9860 KB Output is correct
17 Correct 7 ms 9868 KB Output is correct
18 Correct 8 ms 9888 KB Output is correct
19 Correct 9 ms 9872 KB Output is correct
20 Correct 7 ms 9804 KB Output is correct
21 Correct 9 ms 9864 KB Output is correct
22 Correct 7 ms 9876 KB Output is correct
23 Correct 8 ms 9932 KB Output is correct
24 Correct 7 ms 9864 KB Output is correct
25 Correct 7 ms 9868 KB Output is correct
26 Correct 7 ms 9804 KB Output is correct
27 Correct 7 ms 9728 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 31764 KB Output is correct
2 Correct 225 ms 31800 KB Output is correct
3 Correct 167 ms 28140 KB Output is correct
4 Correct 156 ms 25916 KB Output is correct
5 Correct 155 ms 23560 KB Output is correct
6 Correct 121 ms 22628 KB Output is correct
7 Correct 108 ms 22152 KB Output is correct
8 Correct 102 ms 21688 KB Output is correct
9 Correct 107 ms 21548 KB Output is correct
10 Correct 96 ms 21300 KB Output is correct
11 Correct 94 ms 21132 KB Output is correct
12 Correct 91 ms 20932 KB Output is correct
13 Correct 93 ms 20744 KB Output is correct
14 Correct 102 ms 24040 KB Output is correct
15 Correct 195 ms 35348 KB Output is correct
16 Correct 193 ms 33484 KB Output is correct
17 Correct 206 ms 33068 KB Output is correct
18 Correct 193 ms 30928 KB Output is correct
19 Correct 158 ms 25912 KB Output is correct
20 Correct 160 ms 25652 KB Output is correct
21 Correct 154 ms 25468 KB Output is correct
22 Correct 125 ms 23824 KB Output is correct
23 Correct 126 ms 22596 KB Output is correct
24 Correct 160 ms 29536 KB Output is correct
25 Correct 172 ms 29368 KB Output is correct
26 Correct 161 ms 27916 KB Output is correct
27 Correct 163 ms 27256 KB Output is correct

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 -