oj.uz

Submission #404330

# Submission time Handle Problem Language Result Execution time Memory
404330 2021-05-14T08:14:35 Z kshitij_sodani Duathlon (APIO18_duathlon) C++14
31 / 100
 237 ms 41052 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+=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

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 7 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 7 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 39336 KB Output is correct
2 Correct 103 ms 39328 KB Output is correct
3 Correct 152 ms 32404 KB Output is correct
4 Correct 125 ms 41052 KB Output is correct
5 Correct 119 ms 29152 KB Output is correct
6 Correct 152 ms 32544 KB Output is correct
7 Correct 150 ms 31608 KB Output is correct
8 Correct 165 ms 33292 KB Output is correct
9 Correct 186 ms 28276 KB Output is correct
10 Correct 156 ms 28620 KB Output is correct
11 Correct 102 ms 24516 KB Output is correct
12 Correct 116 ms 24448 KB Output is correct
13 Correct 95 ms 24336 KB Output is correct
14 Correct 110 ms 24120 KB Output is correct
15 Correct 91 ms 23628 KB Output is correct
16 Correct 84 ms 23236 KB Output is correct
17 Correct 28 ms 17496 KB Output is correct
18 Correct 26 ms 17492 KB Output is correct
19 Correct 24 ms 17564 KB Output is correct
20 Correct 23 ms 17524 KB Output is correct
21 Correct 24 ms 17472 KB Output is correct
22 Correct 23 ms 17484 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9880 KB Output is correct
2 Correct 6 ms 9932 KB Output is correct
3 Correct 6 ms 9932 KB Output is correct
4 Correct 7 ms 10060 KB Output is correct
5 Correct 7 ms 9932 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 9932 KB Output is correct
9 Correct 7 ms 10004 KB Output is correct
10 Correct 7 ms 9932 KB Output is correct
11 Correct 7 ms 9868 KB Output is correct
12 Correct 7 ms 9932 KB Output is correct
13 Correct 8 ms 9932 KB Output is correct
14 Correct 8 ms 9916 KB Output is correct
15 Correct 7 ms 9932 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 6 ms 9932 KB Output is correct
20 Correct 7 ms 9876 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 31396 KB Output is correct
2 Correct 203 ms 32684 KB Output is correct
3 Correct 186 ms 32584 KB Output is correct
4 Correct 188 ms 32636 KB Output is correct
5 Correct 237 ms 32688 KB Output is correct
6 Correct 189 ms 40620 KB Output is correct
7 Correct 201 ms 38172 KB Output is correct
8 Correct 212 ms 36660 KB Output is correct
9 Correct 186 ms 35280 KB Output is correct
10 Correct 205 ms 32504 KB Output is correct
11 Correct 185 ms 32512 KB Output is correct
12 Correct 198 ms 32052 KB Output is correct
13 Correct 186 ms 32064 KB Output is correct
14 Correct 138 ms 30532 KB Output is correct
15 Correct 158 ms 29248 KB Output is correct
16 Correct 90 ms 25244 KB Output is correct
17 Correct 161 ms 34492 KB Output is correct
18 Correct 154 ms 33796 KB Output is correct
19 Correct 156 ms 33576 KB Output is correct
20 Correct 153 ms 33276 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 31356 KB Output is correct
2 Correct 181 ms 32564 KB Output is correct
3 Incorrect 182 ms 29148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 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 7 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -