oj.uz

Submission #404040

# Submission time Handle Problem Language Result Execution time Memory
404040 2021-05-13T17:14:36 Z kshitij_sodani Duathlon (APIO18_duathlon) C++14
31 / 100
 1000 ms 38456 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);
							//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 95 ms 33416 KB Output is correct
2 Correct 118 ms 33332 KB Output is correct
3 Correct 114 ms 32312 KB Output is correct
4 Correct 107 ms 34152 KB Output is correct
5 Correct 112 ms 27948 KB Output is correct
6 Correct 142 ms 30904 KB Output is correct
7 Correct 128 ms 29300 KB Output is correct
8 Correct 119 ms 30592 KB Output is correct
9 Correct 120 ms 27664 KB Output is correct
10 Correct 131 ms 27720 KB Output is correct
11 Correct 91 ms 24148 KB Output is correct
12 Correct 93 ms 24240 KB Output is correct
13 Correct 85 ms 24156 KB Output is correct
14 Correct 85 ms 23876 KB Output is correct
15 Correct 72 ms 23672 KB Output is correct
16 Correct 70 ms 23300 KB Output is correct
17 Correct 18 ms 17548 KB Output is correct
18 Correct 18 ms 17484 KB Output is correct
19 Correct 18 ms 17460 KB Output is correct
20 Correct 18 ms 17552 KB Output is correct
21 Correct 18 ms 17504 KB Output is correct
22 Correct 19 ms 17460 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 9932 KB Output is correct
3 Correct 7 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 8 ms 10020 KB Output is correct
7 Correct 7 ms 9932 KB Output is correct
8 Correct 7 ms 10012 KB Output is correct
9 Correct 8 ms 9932 KB Output is correct
10 Correct 7 ms 9932 KB Output is correct
11 Correct 8 ms 9932 KB Output is correct
12 Correct 7 ms 9932 KB Output is correct
13 Correct 7 ms 9932 KB Output is correct
14 Correct 6 ms 9932 KB Output is correct
15 Correct 6 ms 9924 KB Output is correct
16 Correct 7 ms 9900 KB Output is correct
17 Correct 7 ms 9880 KB Output is correct
18 Correct 6 ms 9932 KB Output is correct
19 Correct 6 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 132 ms 31332 KB Output is correct
2 Correct 159 ms 31392 KB Output is correct
3 Correct 134 ms 31416 KB Output is correct
4 Correct 128 ms 31424 KB Output is correct
5 Correct 154 ms 31412 KB Output is correct
6 Correct 156 ms 38456 KB Output is correct
7 Correct 145 ms 36436 KB Output is correct
8 Correct 141 ms 35052 KB Output is correct
9 Correct 161 ms 33736 KB Output is correct
10 Correct 161 ms 31064 KB Output is correct
11 Correct 151 ms 31336 KB Output is correct
12 Correct 157 ms 30924 KB Output is correct
13 Correct 159 ms 30836 KB Output is correct
14 Correct 120 ms 29476 KB Output is correct
15 Correct 128 ms 28236 KB Output is correct
16 Correct 99 ms 24696 KB Output is correct
17 Correct 154 ms 31576 KB Output is correct
18 Correct 154 ms 31524 KB Output is correct
19 Correct 141 ms 31644 KB Output is correct
20 Correct 138 ms 31600 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 9888 KB Output is correct
3 Incorrect 11 ms 9944 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 31444 KB Output is correct
2 Correct 154 ms 31288 KB Output is correct
3 Execution timed out 1098 ms 28400 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 -