oj.uz

Submission #404347

# Submission time Handle Problem Language Result Execution time Memory
404347 2021-05-14T08:41:18 Z kshitij_sodani Duathlon (APIO18_duathlon) C++14
71 / 100
 1000 ms 988420 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];
vector<llo> adj3[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 ok=0;
void dfs3(int no){
	vis[no]=1;
	/*if(ok){
		cout<<no<<'?'<<vis[no]<<endl;
	}*/
	for(auto j:adj3[no]){
		/*if(ok==1){
			cout<<no<<",,"<<j<<"::"<<vis[j]<<endl;
		}*/
		//dfs3(j);
		if(vis[j]==0){
			/*if(ok==1){
				cout<<no<<",,"<<j<<"::"<<vis[j]<<endl;
				dfs3(j);
			}*/
			dfs3(j);
			//if(ok==1){
			//	cout<<no<<",,"<<j<<"::"<<vis[j]<<endl;
			//}
		}
	}
}
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);
	}
	if(n<=10){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				for(int k=0;k<n;k++){
					if(i==j or i==k or j==k){
						continue;
					}
					for(int ii=0;ii<(1<<n);ii++){
						int aa=ii;
						int bb=(1<<n)-1-aa;
						if(aa&(1<<j)){
							bb+=(1<<j);
						}
						else{
							aa+=(1<<j);
						}
						for(int mm=0;mm<n;mm++){
							adj3[mm].clear();
							vis[mm]=0;
						}
						for(int mm=0;mm<n;mm++){
							for(auto jj:adj[mm]){
								
								if(((1<<mm)&aa) and ((1<<jj)&aa)){
									/*if(i==0 and j==1 and k==2 and ii==3){
										cout<<mm<<","<<jj<<endl;
									}*/
									adj3[mm].pb(jj);
								}
							}
						}
						//for(int )
						
						dfs3(i);
						
						if(vis[j]){
							for(int mm=0;mm<n;mm++){
								adj3[mm].clear();
								vis[mm]=0;
							}
							for(int mm=0;mm<n;mm++){
								for(auto jj:adj[mm]){
									if(((1<<mm)&bb) and ((1<<jj)&bb)){
										adj3[mm].pb(jj);
									}
								}
							}
							dfs3(j);
							if(vis[k]){
								ans++;
								break;
							}
						}

					}
				}
			}
		}
		cout<<ans<<endl;
		return 0;
	}
	
	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:223:10: warning: unused variable 'co2' [-Wunused-variable]
  223 |      llo co2=0;
      |          ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 9 ms 11980 KB Output is correct
3 Correct 8 ms 12080 KB Output is correct
4 Correct 8 ms 12024 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 40 ms 12108 KB Output is correct
7 Correct 76 ms 12080 KB Output is correct
8 Correct 71 ms 12152 KB Output is correct
9 Correct 23 ms 12104 KB Output is correct
10 Correct 28 ms 12104 KB Output is correct
11 Correct 84 ms 12080 KB Output is correct
12 Correct 82 ms 12084 KB Output is correct
13 Correct 87 ms 12072 KB Output is correct
14 Correct 62 ms 11980 KB Output is correct
15 Correct 73 ms 12072 KB Output is correct
16 Correct 59 ms 12084 KB Output is correct
17 Correct 49 ms 11980 KB Output is correct
18 Correct 53 ms 11980 KB Output is correct
19 Correct 56 ms 12084 KB Output is correct
20 Correct 49 ms 12088 KB Output is correct
21 Correct 44 ms 11980 KB Output is correct
22 Correct 93 ms 12068 KB Output is correct
23 Correct 30 ms 12088 KB Output is correct
24 Correct 14 ms 11980 KB Output is correct
25 Correct 30 ms 11980 KB Output is correct
26 Correct 81 ms 11980 KB Output is correct
27 Correct 13 ms 11980 KB Output is correct
28 Correct 33 ms 12088 KB Output is correct
29 Correct 90 ms 12072 KB Output is correct
30 Correct 13 ms 12080 KB Output is correct
31 Correct 24 ms 11980 KB Output is correct
32 Correct 81 ms 12080 KB Output is correct
33 Correct 35 ms 11980 KB Output is correct
34 Correct 36 ms 11980 KB Output is correct
35 Correct 64 ms 12100 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 9 ms 11980 KB Output is correct
3 Correct 8 ms 12080 KB Output is correct
4 Correct 8 ms 12024 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 40 ms 12108 KB Output is correct
7 Correct 76 ms 12080 KB Output is correct
8 Correct 71 ms 12152 KB Output is correct
9 Correct 23 ms 12104 KB Output is correct
10 Correct 28 ms 12104 KB Output is correct
11 Correct 84 ms 12080 KB Output is correct
12 Correct 82 ms 12084 KB Output is correct
13 Correct 87 ms 12072 KB Output is correct
14 Correct 62 ms 11980 KB Output is correct
15 Correct 73 ms 12072 KB Output is correct
16 Correct 59 ms 12084 KB Output is correct
17 Correct 49 ms 11980 KB Output is correct
18 Correct 53 ms 11980 KB Output is correct
19 Correct 56 ms 12084 KB Output is correct
20 Correct 49 ms 12088 KB Output is correct
21 Correct 44 ms 11980 KB Output is correct
22 Correct 93 ms 12068 KB Output is correct
23 Correct 30 ms 12088 KB Output is correct
24 Correct 14 ms 11980 KB Output is correct
25 Correct 30 ms 11980 KB Output is correct
26 Correct 81 ms 11980 KB Output is correct
27 Correct 13 ms 11980 KB Output is correct
28 Correct 33 ms 12088 KB Output is correct
29 Correct 90 ms 12072 KB Output is correct
30 Correct 13 ms 12080 KB Output is correct
31 Correct 24 ms 11980 KB Output is correct
32 Correct 81 ms 12080 KB Output is correct
33 Correct 35 ms 11980 KB Output is correct
34 Correct 36 ms 11980 KB Output is correct
35 Correct 64 ms 12100 KB Output is correct
36 Correct 8 ms 12088 KB Output is correct
37 Correct 7 ms 12016 KB Output is correct
38 Execution timed out 1130 ms 988420 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 42916 KB Output is correct
2 Correct 110 ms 43028 KB Output is correct
3 Correct 153 ms 36000 KB Output is correct
4 Correct 158 ms 43284 KB Output is correct
5 Correct 146 ms 31520 KB Output is correct
6 Correct 165 ms 34836 KB Output is correct
7 Correct 168 ms 34092 KB Output is correct
8 Correct 165 ms 35540 KB Output is correct
9 Correct 173 ms 30604 KB Output is correct
10 Correct 171 ms 30872 KB Output is correct
11 Correct 119 ms 26800 KB Output is correct
12 Correct 111 ms 26820 KB Output is correct
13 Correct 103 ms 26680 KB Output is correct
14 Correct 128 ms 26464 KB Output is correct
15 Correct 90 ms 25916 KB Output is correct
16 Correct 96 ms 25632 KB Output is correct
17 Correct 25 ms 19864 KB Output is correct
18 Correct 26 ms 19884 KB Output is correct
19 Correct 31 ms 19868 KB Output is correct
20 Correct 28 ms 19804 KB Output is correct
21 Correct 32 ms 19780 KB Output is correct
22 Correct 30 ms 19904 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12236 KB Output is correct
2 Correct 11 ms 12240 KB Output is correct
3 Correct 10 ms 12240 KB Output is correct
4 Correct 10 ms 12344 KB Output is correct
5 Correct 11 ms 12364 KB Output is correct
6 Correct 10 ms 12340 KB Output is correct
7 Correct 11 ms 12340 KB Output is correct
8 Correct 9 ms 12364 KB Output is correct
9 Correct 9 ms 12364 KB Output is correct
10 Correct 9 ms 12236 KB Output is correct
11 Correct 9 ms 12272 KB Output is correct
12 Correct 9 ms 12236 KB Output is correct
13 Correct 9 ms 12216 KB Output is correct
14 Correct 9 ms 12236 KB Output is correct
15 Correct 9 ms 12236 KB Output is correct
16 Correct 9 ms 12212 KB Output is correct
17 Correct 9 ms 12344 KB Output is correct
18 Correct 9 ms 12344 KB Output is correct
19 Correct 9 ms 12280 KB Output is correct
20 Correct 10 ms 12252 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 35008 KB Output is correct
2 Correct 190 ms 35016 KB Output is correct
3 Correct 193 ms 34964 KB Output is correct
4 Correct 188 ms 35016 KB Output is correct
5 Correct 189 ms 34996 KB Output is correct
6 Correct 215 ms 42960 KB Output is correct
7 Correct 200 ms 40480 KB Output is correct
8 Correct 225 ms 39052 KB Output is correct
9 Correct 197 ms 37608 KB Output is correct
10 Correct 211 ms 34684 KB Output is correct
11 Correct 191 ms 34920 KB Output is correct
12 Correct 193 ms 34424 KB Output is correct
13 Correct 198 ms 34416 KB Output is correct
14 Correct 147 ms 32892 KB Output is correct
15 Correct 141 ms 31656 KB Output is correct
16 Correct 99 ms 27508 KB Output is correct
17 Correct 168 ms 36864 KB Output is correct
18 Correct 173 ms 36212 KB Output is correct
19 Correct 161 ms 35928 KB Output is correct
20 Correct 177 ms 35644 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12236 KB Output is correct
2 Correct 9 ms 12320 KB Output is correct
3 Correct 9 ms 12220 KB Output is correct
4 Correct 11 ms 12236 KB Output is correct
5 Correct 8 ms 12216 KB Output is correct
6 Correct 9 ms 12216 KB Output is correct
7 Correct 9 ms 12232 KB Output is correct
8 Correct 10 ms 12228 KB Output is correct
9 Correct 9 ms 12108 KB Output is correct
10 Correct 9 ms 12236 KB Output is correct
11 Correct 8 ms 12160 KB Output is correct
12 Correct 10 ms 12364 KB Output is correct
13 Correct 8 ms 12236 KB Output is correct
14 Correct 9 ms 12236 KB Output is correct
15 Correct 8 ms 12212 KB Output is correct
16 Correct 9 ms 12216 KB Output is correct
17 Correct 9 ms 12216 KB Output is correct
18 Correct 9 ms 12256 KB Output is correct
19 Correct 8 ms 12180 KB Output is correct
20 Correct 10 ms 12220 KB Output is correct
21 Correct 9 ms 12236 KB Output is correct
22 Correct 9 ms 12236 KB Output is correct
23 Correct 9 ms 12212 KB Output is correct
24 Correct 9 ms 12236 KB Output is correct
25 Correct 9 ms 12196 KB Output is correct
26 Correct 9 ms 12172 KB Output is correct
27 Correct 8 ms 12108 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 34968 KB Output is correct
2 Correct 206 ms 34916 KB Output is correct
3 Correct 198 ms 31384 KB Output is correct
4 Correct 165 ms 28280 KB Output is correct
5 Correct 131 ms 25912 KB Output is correct
6 Correct 127 ms 24948 KB Output is correct
7 Correct 114 ms 24516 KB Output is correct
8 Correct 109 ms 23980 KB Output is correct
9 Correct 104 ms 23892 KB Output is correct
10 Correct 104 ms 23704 KB Output is correct
11 Correct 101 ms 23468 KB Output is correct
12 Correct 96 ms 23352 KB Output is correct
13 Correct 89 ms 23096 KB Output is correct
14 Correct 100 ms 26608 KB Output is correct
15 Correct 193 ms 37676 KB Output is correct
16 Correct 195 ms 35648 KB Output is correct
17 Correct 177 ms 35336 KB Output is correct
18 Correct 182 ms 33336 KB Output is correct
19 Correct 166 ms 28376 KB Output is correct
20 Correct 171 ms 28032 KB Output is correct
21 Correct 159 ms 27780 KB Output is correct
22 Correct 120 ms 26212 KB Output is correct
23 Correct 112 ms 24900 KB Output is correct
24 Correct 164 ms 31784 KB Output is correct
25 Correct 197 ms 31780 KB Output is correct
26 Correct 152 ms 30120 KB Output is correct
27 Correct 165 ms 29620 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 9 ms 11980 KB Output is correct
3 Correct 8 ms 12080 KB Output is correct
4 Correct 8 ms 12024 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 40 ms 12108 KB Output is correct
7 Correct 76 ms 12080 KB Output is correct
8 Correct 71 ms 12152 KB Output is correct
9 Correct 23 ms 12104 KB Output is correct
10 Correct 28 ms 12104 KB Output is correct
11 Correct 84 ms 12080 KB Output is correct
12 Correct 82 ms 12084 KB Output is correct
13 Correct 87 ms 12072 KB Output is correct
14 Correct 62 ms 11980 KB Output is correct
15 Correct 73 ms 12072 KB Output is correct
16 Correct 59 ms 12084 KB Output is correct
17 Correct 49 ms 11980 KB Output is correct
18 Correct 53 ms 11980 KB Output is correct
19 Correct 56 ms 12084 KB Output is correct
20 Correct 49 ms 12088 KB Output is correct
21 Correct 44 ms 11980 KB Output is correct
22 Correct 93 ms 12068 KB Output is correct
23 Correct 30 ms 12088 KB Output is correct
24 Correct 14 ms 11980 KB Output is correct
25 Correct 30 ms 11980 KB Output is correct
26 Correct 81 ms 11980 KB Output is correct
27 Correct 13 ms 11980 KB Output is correct
28 Correct 33 ms 12088 KB Output is correct
29 Correct 90 ms 12072 KB Output is correct
30 Correct 13 ms 12080 KB Output is correct
31 Correct 24 ms 11980 KB Output is correct
32 Correct 81 ms 12080 KB Output is correct
33 Correct 35 ms 11980 KB Output is correct
34 Correct 36 ms 11980 KB Output is correct
35 Correct 64 ms 12100 KB Output is correct
36 Correct 8 ms 12088 KB Output is correct
37 Correct 7 ms 12016 KB Output is correct
38 Execution timed out 1130 ms 988420 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 9 ms 11980 KB Output is correct
3 Correct 8 ms 12080 KB Output is correct
4 Correct 8 ms 12024 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 40 ms 12108 KB Output is correct
7 Correct 76 ms 12080 KB Output is correct
8 Correct 71 ms 12152 KB Output is correct
9 Correct 23 ms 12104 KB Output is correct
10 Correct 28 ms 12104 KB Output is correct
11 Correct 84 ms 12080 KB Output is correct
12 Correct 82 ms 12084 KB Output is correct
13 Correct 87 ms 12072 KB Output is correct
14 Correct 62 ms 11980 KB Output is correct
15 Correct 73 ms 12072 KB Output is correct
16 Correct 59 ms 12084 KB Output is correct
17 Correct 49 ms 11980 KB Output is correct
18 Correct 53 ms 11980 KB Output is correct
19 Correct 56 ms 12084 KB Output is correct
20 Correct 49 ms 12088 KB Output is correct
21 Correct 44 ms 11980 KB Output is correct
22 Correct 93 ms 12068 KB Output is correct
23 Correct 30 ms 12088 KB Output is correct
24 Correct 14 ms 11980 KB Output is correct
25 Correct 30 ms 11980 KB Output is correct
26 Correct 81 ms 11980 KB Output is correct
27 Correct 13 ms 11980 KB Output is correct
28 Correct 33 ms 12088 KB Output is correct
29 Correct 90 ms 12072 KB Output is correct
30 Correct 13 ms 12080 KB Output is correct
31 Correct 24 ms 11980 KB Output is correct
32 Correct 81 ms 12080 KB Output is correct
33 Correct 35 ms 11980 KB Output is correct
34 Correct 36 ms 11980 KB Output is correct
35 Correct 64 ms 12100 KB Output is correct
36 Correct 8 ms 12088 KB Output is correct
37 Correct 7 ms 12016 KB Output is correct
38 Execution timed out 1130 ms 988420 KB Time limit exceeded
39 Halted 0 ms 0 KB -