oj.uz

Submission #404315

# Submission time Handle Problem Language Result Execution time Memory
404315 2021-05-14T07:28:44 Z kshitij_sodani Duathlon (APIO18_duathlon) C++14
31 / 100
 1000 ms 39776 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;		
						}
						for(auto ii:pre[j]){
							pa=par[ii];
							co5=0;
							dfs3(ii);
							ans+=2*((co5-1)*(aa-1)*(aa-1));
							//cout<<ii<<":"<<co5<<endl;
							//cout<<ii<<":"<<co5[ii]<<endl;
					//		cout<<ii<<":"<<(aa-1)*2*(ss.size()-co5-(aa-1))<<endl;
						//	ans+=(aa-1)*2*(ss.size()-co5-(aa-1));
							continue;
							if(ii!=j){
								llo co=ss.size();
								co-=aa;
								
								for(auto k:adj[ii]){
									if(k!=par5[ii] and par[k]!=par[ii]){
										co-=val[k];
										co2+=val[k];
									}
								}
								ans+=2*(aa-1)*co;
							//	cout<<ii<<":"<<(2*(aa-1))*co<<":"<<co<<endl;

							}
						}
						//ans+=2*(aa-1)*co2;
						//cout<<j<<":"<<(2*(aa-1))*co2<<endl;
					}
				}
			}



		}
	}
	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 92 ms 34632 KB Output is correct
2 Correct 93 ms 34668 KB Output is correct
3 Correct 141 ms 33648 KB Output is correct
4 Correct 107 ms 35436 KB Output is correct
5 Correct 121 ms 29236 KB Output is correct
6 Correct 122 ms 32068 KB Output is correct
7 Correct 128 ms 30560 KB Output is correct
8 Correct 123 ms 31900 KB Output is correct
9 Correct 120 ms 28884 KB Output is correct
10 Correct 111 ms 28992 KB Output is correct
11 Correct 95 ms 25412 KB Output is correct
12 Correct 102 ms 25284 KB Output is correct
13 Correct 92 ms 25132 KB Output is correct
14 Correct 86 ms 24840 KB Output is correct
15 Correct 72 ms 24292 KB Output is correct
16 Correct 70 ms 24076 KB Output is correct
17 Correct 18 ms 17552 KB Output is correct
18 Correct 18 ms 17484 KB Output is correct
19 Correct 18 ms 17568 KB Output is correct
20 Correct 18 ms 17452 KB Output is correct
21 Correct 18 ms 17544 KB Output is correct
22 Correct 18 ms 17528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9932 KB Output is correct
2 Correct 7 ms 9976 KB Output is correct
3 Correct 7 ms 9864 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 9992 KB Output is correct
10 Correct 7 ms 9888 KB Output is correct
11 Correct 7 ms 9932 KB Output is correct
12 Correct 8 ms 9932 KB Output is correct
13 Correct 7 ms 9868 KB Output is correct
14 Correct 7 ms 9932 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 7 ms 9932 KB Output is correct
20 Correct 7 ms 9932 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 32704 KB Output is correct
2 Correct 143 ms 32692 KB Output is correct
3 Correct 136 ms 32712 KB Output is correct
4 Correct 135 ms 32636 KB Output is correct
5 Correct 135 ms 32692 KB Output is correct
6 Correct 148 ms 39776 KB Output is correct
7 Correct 144 ms 37560 KB Output is correct
8 Correct 143 ms 36304 KB Output is correct
9 Correct 140 ms 35048 KB Output is correct
10 Correct 135 ms 32364 KB Output is correct
11 Correct 134 ms 32596 KB Output is correct
12 Correct 139 ms 32064 KB Output is correct
13 Correct 148 ms 32076 KB Output is correct
14 Correct 123 ms 30608 KB Output is correct
15 Correct 110 ms 29324 KB Output is correct
16 Correct 76 ms 25236 KB Output is correct
17 Correct 134 ms 32788 KB Output is correct
18 Correct 130 ms 32808 KB Output is correct
19 Correct 133 ms 32844 KB Output is correct
20 Correct 132 ms 32892 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 32632 KB Output is correct
2 Correct 144 ms 32536 KB Output is correct
3 Execution timed out 1089 ms 29756 KB Time limit exceeded
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 -