oj.uz

Submission #738522

# Submission time Handle Problem Language Result Execution time Memory
738522 2023-05-09T02:30:36 Z 089487 Duathlon (APIO18_duathlon) C++14
0 / 100
 92 ms 28200 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];
int in[N];
int low[N];
int t=1;
int num=0;
int group[N];
int sz[N];
bool cut[N];
stack<int> st;
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();
			group[x2]=num;
			sz[num]++;
			if(x2==x) break;
		}
		cut[num]=ct;
	}
}
pii e[N];
int sum;
int Sz[N];
bool vis[N];
void dfs_sz(int x,int p=-1){
	Sz[x]=sz[x];
	for(int i:v2[x]){
		if(i!=p){
			dfs_sz(i,x);
			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){
	int a=Sz[x]-sz[x];
	int b=sum-Sz[x];
	int c=sz[x];
	vis[x]=true;
	ans+=a*b*c*2+C2(c)*(a+b)*2+C3(c);
	int s=0;
	for(int i:v2[x]){
		if(cut[x]){
			ans+=C2(sz[i]);
		}
		if(i!=p){
			solve(i,x);
			ans+=s*Sz[i]*c*2;
			s+=sz[i];
		}
	}
}
signed main(){
	quick
	int n,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);
	}
	dfs(1);
	rep(i,1,m){
		int g1=group[e[i].F];
		int g2=group[e[i].S];
		if(g1!=g2){
			v2[g1].eb(g2);
			v2[g2].eb(g1);
		}
	}
	rep(i,1,num) sort(all(v2[i])),v2[i].erase(unique(all(v2[i])),v2[i].end());
	ans=0;
	rep(i,1,num){
		if(!Sz[i]){
			dfs_sz(i);
			solve(i);
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9736 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 6 ms 9728 KB Output is correct
7 Incorrect 6 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9736 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 6 ms 9728 KB Output is correct
7 Incorrect 6 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 28188 KB Output is correct
2 Correct 92 ms 28200 KB Output is correct
3 Incorrect 84 ms 23116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 24132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 24068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9736 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 6 ms 9728 KB Output is correct
7 Incorrect 6 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9736 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 6 ms 9728 KB Output is correct
7 Incorrect 6 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -