oj.uz

Submission #739128

# Submission time Handle Problem Language Result Execution time Memory
739128 2023-05-10T02:58:24 Z 089487 Duathlon (APIO18_duathlon) C++14
0 / 100
 1000 ms 41664 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
    cout<<a<<" ",debug(b...);
}
const int N=2e5+7;
const int INF=1e18;
vector<int> v[N];
vector<int> v2[N];
vector<int> v3[N];
int in[N];
int low[N];
int t=1;
int num;
int sz[N];
bool cut[N];
stack<int> st;
void add_edge(int a,int b){
	v2[a].eb(b);
	v2[b].eb(a);
	//debug(a,"<->",b);
}
void dfs(int x,int p=-1){
	in[x]=low[x]=t++;
	st.push(x);
	bool ct=false;
	for(int i:v[x]){
		if(i==p) continue;
		if(in[i]) low[x]=min(low[x],in[i]);
		else{
			dfs(i,x);
			if(in[x]<=low[i]) ct=true;
			low[x]=min(low[x],low[i]);
		}
	}
	if(p==-1){
		ct=(sz(v[x])>=2);
	}
	if(p==-1||in[p]<=low[x]){
		++num;
		while(sz(st)){
			int x2=st.top();
			st.pop();
			add_edge(num,x2);
			if(x2==x) break;
		}
		if(p!=-1)add_edge(num,p);
		cut[num]=ct;
	}
}
pii e[N];
int sum;
int n;
int Sz[N];
int Sz2[N];
bool vis[N];
int fa[N];
int dep[N];
void dfs_sz(int x,int p=-1,int d=0){
	dep[x]=d;
	Sz[x]=sz[x];
	for(int i:v2[x]){
		if(i!=p){
			dfs_sz(i,x,d+1);
			Sz[x]+=Sz[i];
		}
	}
	sum=Sz[x];
}
int C2(int x){
	if(x<2) return 0;
	return x*(x-1);
}
int C3(int x){
	if(x<3) return 0;
	return x*(x-1)*(x-2);
}
int ans=0;
void solve(int x,int p=-1){
	fa[x]=p;
	vis[x]=true;
	for(int i:v2[x]){
		if(!vis[i]) solve(i,x);
	}
	if(x<=n){
		int s=0;
 
		// 1
		for(int i:v2[x]){
			int S2;
						
			if(i==p){
				S2=sum-Sz[x];
			}
			else{
				S2=Sz[i];	
			}
			ans+=s*S2*2;
			s+=S2;
			//ans+=C2(S2);
		}
		/*for(int i:v2[x]){
			for(int j:v2[i]){
				if(j==x) continue;
				int S2;
				if(dep[j]<dep[i]){
					S2=sum-Sz[j];
				}
				else{
 
				}
			}
		}*/
	}
	else{
		int l=sz(v2[x]);
		for(int i:v2[x]){
			int S2;
			if(i==p){
				S2=sum-Sz[x];
			}
			else{
				S2=Sz[i];
			}
			for(int j:v2[x]){
				int S3;
				if(i==j) continue;
				if(j==p){
					S3=sum-Sz[x];
				}
				else{
					S3=Sz[j];
				}
				ans+=S2*S3*(l-2);
			}
		}	
	}
}
signed main(){
	quick
	int m;
	cin>>n>>m;
	rep(i,1,m){
		cin>>e[i].F>>e[i].S;
		v[e[i].F].eb(e[i].S);
		v[e[i].S].eb(e[i].F);
	}
	num=n;
	dfs(1);
	rep(i,1,n) sz[i]=1;
	ans=0;
	rep(i,1,num){
		if(!vis[i]){
			dfs_sz(i);
			solve(i);
		}
	}
	//rep(i,1,n) cout<<Sz[i]<<" \n"[i==n];
	cout<<ans<<"\n";
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14428 KB Output is correct
2 Correct 9 ms 14440 KB Output is correct
3 Correct 11 ms 14440 KB Output is correct
4 Correct 9 ms 14428 KB Output is correct
5 Correct 8 ms 14428 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 9 ms 14432 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 9 ms 14420 KB Output is correct
13 Correct 9 ms 14420 KB Output is correct
14 Correct 9 ms 14420 KB Output is correct
15 Correct 9 ms 14432 KB Output is correct
16 Correct 9 ms 14456 KB Output is correct
17 Correct 8 ms 14356 KB Output is correct
18 Correct 9 ms 14420 KB Output is correct
19 Incorrect 8 ms 14420 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14428 KB Output is correct
2 Correct 9 ms 14440 KB Output is correct
3 Correct 11 ms 14440 KB Output is correct
4 Correct 9 ms 14428 KB Output is correct
5 Correct 8 ms 14428 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 9 ms 14432 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 9 ms 14420 KB Output is correct
13 Correct 9 ms 14420 KB Output is correct
14 Correct 9 ms 14420 KB Output is correct
15 Correct 9 ms 14432 KB Output is correct
16 Correct 9 ms 14456 KB Output is correct
17 Correct 8 ms 14356 KB Output is correct
18 Correct 9 ms 14420 KB Output is correct
19 Incorrect 8 ms 14420 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 40732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14564 KB Output is correct
2 Correct 10 ms 14564 KB Output is correct
3 Correct 9 ms 14676 KB Output is correct
4 Correct 10 ms 14764 KB Output is correct
5 Correct 9 ms 14756 KB Output is correct
6 Correct 10 ms 14676 KB Output is correct
7 Correct 9 ms 14676 KB Output is correct
8 Correct 9 ms 14676 KB Output is correct
9 Correct 11 ms 14676 KB Output is correct
10 Incorrect 9 ms 14548 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 34160 KB Output is correct
2 Correct 141 ms 34192 KB Output is correct
3 Correct 124 ms 34096 KB Output is correct
4 Correct 114 ms 34112 KB Output is correct
5 Correct 107 ms 34172 KB Output is correct
6 Correct 128 ms 41664 KB Output is correct
7 Correct 123 ms 39472 KB Output is correct
8 Correct 127 ms 37956 KB Output is correct
9 Correct 123 ms 36684 KB Output is correct
10 Incorrect 84 ms 30080 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14676 KB Output is correct
2 Correct 9 ms 14564 KB Output is correct
3 Correct 9 ms 14676 KB Output is correct
4 Correct 10 ms 14572 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 9 ms 14548 KB Output is correct
7 Correct 12 ms 14548 KB Output is correct
8 Correct 11 ms 14548 KB Output is correct
9 Correct 10 ms 14568 KB Output is correct
10 Correct 12 ms 14540 KB Output is correct
11 Correct 11 ms 14548 KB Output is correct
12 Correct 10 ms 14676 KB Output is correct
13 Correct 10 ms 14704 KB Output is correct
14 Correct 9 ms 14676 KB Output is correct
15 Correct 9 ms 14676 KB Output is correct
16 Incorrect 10 ms 14564 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 34116 KB Output is correct
2 Correct 136 ms 33956 KB Output is correct
3 Correct 126 ms 33548 KB Output is correct
4 Correct 136 ms 32440 KB Output is correct
5 Correct 133 ms 30728 KB Output is correct
6 Correct 111 ms 29980 KB Output is correct
7 Correct 91 ms 29792 KB Output is correct
8 Correct 101 ms 29260 KB Output is correct
9 Correct 105 ms 29308 KB Output is correct
10 Correct 89 ms 29024 KB Output is correct
11 Correct 97 ms 28980 KB Output is correct
12 Correct 154 ms 28800 KB Output is correct
13 Correct 243 ms 28928 KB Output is correct
14 Execution timed out 1072 ms 31532 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14428 KB Output is correct
2 Correct 9 ms 14440 KB Output is correct
3 Correct 11 ms 14440 KB Output is correct
4 Correct 9 ms 14428 KB Output is correct
5 Correct 8 ms 14428 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 9 ms 14432 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 9 ms 14420 KB Output is correct
13 Correct 9 ms 14420 KB Output is correct
14 Correct 9 ms 14420 KB Output is correct
15 Correct 9 ms 14432 KB Output is correct
16 Correct 9 ms 14456 KB Output is correct
17 Correct 8 ms 14356 KB Output is correct
18 Correct 9 ms 14420 KB Output is correct
19 Incorrect 8 ms 14420 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14428 KB Output is correct
2 Correct 9 ms 14440 KB Output is correct
3 Correct 11 ms 14440 KB Output is correct
4 Correct 9 ms 14428 KB Output is correct
5 Correct 8 ms 14428 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 9 ms 14432 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 9 ms 14420 KB Output is correct
13 Correct 9 ms 14420 KB Output is correct
14 Correct 9 ms 14420 KB Output is correct
15 Correct 9 ms 14432 KB Output is correct
16 Correct 9 ms 14456 KB Output is correct
17 Correct 8 ms 14356 KB Output is correct
18 Correct 9 ms 14420 KB Output is correct
19 Incorrect 8 ms 14420 KB Output isn't correct
20 Halted 0 ms 0 KB -